15-双链表-双链表基本操作

题目

来源

827. 双链表 - AcWing题库

思路

此题我只想说，千万千万别漏了头结点和尾结点，不然根本查不出来是哪里出了问题，因为传入的k会有问题；最左边插入，相当于是在头结点的右边插入（也就是0号节点的右边）；最右边插入相当于是尾节点的左边插入（也就是1号节点的左边）。

又由于idx是从2开始，所以对于题意的k，应该传入k+1。

其余详见代码。

代码

#include<iostream>
using namespace std;
const int N=100010;
int l[N],r[N],e[N],idx;//左端点，右端点，当前值，当前索引//初始化
void init(){//0表示左端点，1表示右端点;相当于0是head,1是nullr[0]=1;l[1]=0;idx=2;//0和1已经使用了
}//在k节点右边插入x
void insertr(int k,int x){e[idx]=x;r[idx]=r[k];l[idx]=k;l[r[k]]=idx;r[k]=idx;idx++;
}//在k节点左边插入x
void insertl(int k,int x){insertr(l[k], x); // 等价于在l[k]的右边插入x
}//删除第k个节点
void del(int k){r[l[k]]=r[k];l[r[k]]=l[k];
}int main(){init();int n;cin>>n;while(n--){string op;cin>>op;if(op=="R"){int x;cin>>x;insertl(1, x); // 在右端点的左边插入，即在l[1]的右边插入}else if(op=="D"){int k;cin>>k;del(k+1);}else if(op=="L"){int x;cin>>x;insertr(0, x); // 在0号节点右边插入;相当于0是head的右边插入}else if(op=="IL"){int k,x;cin>>k>>x;insertl(k+1, x);}else if(op=="IR"){int k,x;cin>>k>>x;insertr(k+1, x);}}for(int i=r[0];i!=1;i=r[i]){ //从head开始cout<<e[i]<<" ";}return 0;
}