AcWing 827. 双链表
原题链接
简单
作者:
月亮_7
,
2024-03-30 11:15:04
,
所有人可见
,
阅读 1
#include <iostream>
using namespace std;
const int N=100010;
int m;
int e[N],l[N],r[N],idx;
//l[i],i点左边的数,r[i] i点右边的数
//初始化
void init()
{
//0表示左端点,1表示右端点,相当于两个头尾指针
r[0]=1;
l[1]=0;
idx=2; //idx 此时已经用掉两个点了
}
//在k的右边插入
void add(int k,int x)
{
e[idx]=x;
l[idx]=k;
r[idx]=r[k];//todo 这边的 k 不加 1 , 输入的时候 k+1 就好
l[r[k]]=idx;//这个要写在前面
r[k]=idx;
idx++;
}
//删除第k 个点
void remove(int k)
{
r[l[k]]=r[k];
l[r[k]]=l[k];
}
int main()
{
int n;
init();
cin >> n;
while(n--)
{
string op;
cin >> op;
int k,x;
if(op=="L")
{
cin >> x;//! 同理 最左边插入就是 在指向 0的数的左边插入就可以了 也就是可以直接在 0的 有右边插入
add(0,x);
}else if(op=="R")
{
cin >> x;
add(l[1],x);//! 0和 1 只是代表 头和尾 所以 最右边插入 只要在 指向 1的 那个点的右边插入就可以了
}else if(op=="D")
{
cin >> k;
remove(k+1);
}else if(op=="IL")
{
cin >> k>> x;
add(l[k+1],x);
}else if(op=="IR")
{
cin >> k >> x;
add(k+1,x);
}
}
for(int i=r[0];i!=1;i=r[i])
cout << e[i] << ' ';
return 0;
}