827. 双链表 - AcWing题库
说难也不难，但是细节比较多。
下面的代码是超时的，因为数据量还是比较大的，超时的主要原因就是最右边插入的时候遍历是非常耗时的(可以维护一个尾节点来解决这个问题)。而且根据题意，其实都不用创建节点之类的操作，全程使用数组就可以了。
#include <iostream> #include <string> using namespace std; struct Node{ Node() = default; Node(int x) : val(x), pre(NULL), next(NULL) {} Node(int x, Node *_pre, Node *_next) : val(x), pre(_pre), next(_next) {} int val; Node *pre, *next; }; Node *idx[100010]; Node *head = new Node; int id = 1; //记录第几个插入 void insert_l(int x){ auto node = new Node(x); node->pre = head; if(head->next) head->next->pre = node; node->next = head->next; head->next = node; idx[id++] = node; } void insert_r(int x){ auto node = new Node(x); auto p = head; while (p->next) p = p->next; node->pre = p; node->next = NULL; p->next = node; idx[id++] = node; } void delete_k(int k){ idx[k]->pre->next = idx[k]->next; if(idx[k]->next) idx[k]->next->pre = idx[k]->pre; delete idx[k]; idx[k] = NULL; } void insert_k_l(int k, int x){ auto node = new Node(x); idx[k]->pre->next = node; node->pre = idx[k]->pre; node->next = idx[k]; idx[k]->pre = node; idx[id++] = node; } void insert_k_r(int k, int x){ auto node = new Node(x); node->next = idx[k]->next; if(idx[k]->next) idx[k]->next->pre = node; idx[k]->next = node; node->pre = idx[k]; idx[id++] = node; } int main(){ int m; cin >> m; cin.ignore(); for(int i = 0; i < m; ++i){ string str; int k, x; cin >> str; if(str == "L"){ cin >> x; insert_l(x); } else if(str == "R"){ cin >> x; insert_r(x); } else if (str == "D"){ cin >> k; delete_k(k);//因为初始化加了两个节点，所以第k个数的下标为k+2-1 } else if (str == "IL"){ cin >> k >> x; insert_k_l(k, x); } else if(str == "IR"){ cin >> k >> x; insert_k_r(k, x); } } auto p = head->next; while (p){ cout << p->val << " "; p = p->next; } cout << endl; return 0; }看了别人的题解之后，才发现自己的想法真的太low了。。。重点是建立前驱、后继的映射关系，以及在插入或者删除节点的同时正确更新映射关系。而我去定义一个节点挨个操作完全就是没必要的。
直接使用数组进行存储，为了防止映射关系更新出错，还是建议画画图模拟一下
#include <iostream> #include <string> using namespace std; const int N = 100010; int idx, e[N], l[N], r[N];//l, r分别代表前驱、后缀，e用来记录节点的值 void init(){ //0、1分别表示head、tail r[0] = 1;//head->next=tail l[1] = 0;//tail->pre=head idx = 2;//首尾两个节点 } void insert_l(int x){//node为新节点 l[idx] = 0;//node->pre = head; r[idx] = r[0];//node->next = head->next; r[0] = idx;//head->next = node l[r[idx]] = idx;//node->next->pre = node e[idx++] = x;//添加节点x } void insert_r(int x){ r[idx] = 1;//node->next = tail l[idx] = l[1];//node->pre = tail->pre r[l[idx]] = idx;//node->pre->next = node l[1] = idx;//tail->pre = node e[idx++] = x; } void delete_k(int k){ r[l[k]] = r[k];//k->pre->next = k->next l[r[k]] = l[k];//k->next->pre = k->pre } void insert_k_l(int k, int x){ l[idx] = l[k];//node->pre = k->pre r[idx] = k;//node->next = k r[l[idx]] = idx;//node->pre->next = node l[k] = idx;//k->pre = node e[idx++] = x; } void insert_k_r(int k, int x){ r[idx] = r[k];//node->next = k->next l[idx] = k;//node->pre = k l[r[idx]] = idx;//node->next->pre = node r[k] = idx;//k->next = node e[idx++] = x; } int main(){ int m; cin >> m; cin.ignore(); init(); for(int i = 0; i < m; ++i){ string str; int k, x; cin >> str; if(str == "L"){ cin >> x; insert_l(x); } else if(str == "R"){ cin >> x; insert_r(x); } else if (str == "D"){ cin >> k; delete_k(k+1);//因为初始化首尾节点，所以有下标偏移 } else if (str == "IL"){ cin >> k >> x; insert_k_l(k+1, x); } else if(str == "IR"){ cin >> k >> x; insert_k_r(k+1, x); } } //1代表尾节点 for(int i = r[0]; i != 1; i = r[i]) cout << e[i] << " "; cout << endl; return 0; }可以发现几个删除的函数其实是类似的，可以合并起来使用一个函数，然后调整一下传参就可以了：
#include <iostream> #include <string> using namespace std; const int N = 100010; int idx = 2, value[N], l[N], r[N];//l, r分别代表前驱、后缀，e用来记录节点的值 void init(){//0、1分别表示head、tail r[0] = 1;//head->next=tail l[1] = 0;//tail->pre=head } void insert(int k, int x){//在第k个节点之后插入新节点node r[idx] = r[k];//node->next = k->next l[idx] = k;//node->pre = k l[r[idx]] = idx;//node->next->pre = node r[k] = idx;//k->next = node value[idx++] = x; } void delete_k(int k){ r[l[k]] = r[k];//k->pre->next = k->next l[r[k]] = l[k];//k->next->pre = k->pre } int main(){ int m; cin >> m; cin.ignore(); init(); for(int i = 0; i < m; ++i){ string str; int k, x; cin >> str; if(str == "L"){ cin >> x; insert(0, x); } else if(str == "R"){ cin >> x; insert(l[1], x);//l[1]是尾节点的前驱 } else if (str == "D"){ cin >> k; delete_k(k+1);//因为初始化首尾节点，所以有下标偏移 } else if (str == "IL"){ cin >> k >> x; insert(l[k+1], x);//前面转化为后面 } else if(str == "IR"){ cin >> k >> x; insert(k+1, x); } } //1代表尾节点 for(int i = r[0]; i != 1; i = r[i]) cout << value[i] << " "; cout << endl; return 0; }