AcWing 827. 双链表
原题链接
简单
作者:
逃离这世俗
,
2022-07-07 20:41:28
,
所有人可见
,
阅读 71
#include <iostream>
using namespace std;
const int maxn=1e5+10;
int idx;//表示当前用到了哪个节点
int l[maxn];//双链表的左指针域
int r[maxn];//双链表的右指针域
int e[maxn];//该结点存放的值
void init(){
//0表示左端点,1表示右端点
r[0]=1,l[1]=0;
idx=2;//0和1都被用过了
}
//在下标是k的点的右边插入x
void add(int k,int x){
e[idx]=x;
r[idx]=r[k];//新节点的右边等于k结点的右边
l[idx]=k;//左指针指向k即可
l[r[k]]=idx;//最后将原本指向k结点的左指针指向新节点idx
r[k]=idx;
idx++;
}
//将第k个插入的数删除
void remove(int k){
r[l[k]]=r[k];//k右指针指向的数赋值给k的上个结点的右指针
l[r[k]]=l[k];//k结点的下一个节点左指针指向k结点的左指针(上一个结点)
}
int main(){
int n;
cin>>n;
init();
while(n--){
string c;
cin>>c;
if(c=="L"){
int x;
cin>>x;
add(0,x);
}else if(c=="R"){
int x;
cin>>x;
add(l[1],x);
}else if(c=="D"){
int k;
cin>>k;
remove(k+1);
}else if(c=="IL"){
int k,x;
cin>>k>>x;
add(l[k+1],x);
}else if(c=="IR"){
int k,x;
cin>>k>>x;
add(k+1,x);
}
}
for(int i=r[0];i!=1;i=r[i]){
cout<<e[i]<<" ";
}
return 0;
}