AcWing 827. 双链表
原题链接
简单
作者:
月下邂逅
,
2024-04-25 15:40:03
,
所有人可见
,
阅读 1
C++ 代码
//比单链表多了指向前一节点的指针
#include<iostream>
#include<cstring>
using namespace std;
const int N=100010;
int e[N],r[N],l[N],idx,x,k;//用数组表示节点的时候会浪费空间,既删除的节点不会被释放
void init()//初始化链表
{
//假设0为头节点,1为尾节点,好处是插入时可以直接找到首尾节点,输出时忽略这两个节点即可
l[1]=0;
r[0]=1;
idx=2;//0和1已经占用
}
void insert_IR(int k,int x)//插入第k个节点的右边,k节点右指针指向新节点,原本k的右节点的左指针指向新节点
// 所有的插入操作都可以用该函数来完成,如:
// 1、L x,表示首节点(0)右侧插入数 x
// 2、R x,表示尾节点(1)的左节点右端插入数 x
// 3、IL k x,表示在第 k个插入的左节点右侧插入一个数 x。
// 4、IR k x,在第k个插入的数右侧插入一个数 x。
{
e[idx]=x;
l[idx]=k;
r[idx]=r[k];
l[r[k]]=idx;
r[k]=idx++;
}
void Del(int k)//k左节点的右指针指向k的右节点,k右节点的左指针指向k的左节点
{
r[l[k]]=r[k];
l[r[k]]=l[k];
}
void printNode()
{
for(int i=r[0];i!=1;i=r[i])
{
printf("%d ",e[i]);
}
}
int main()
{
int n;
string s;
scanf("%d",&n);
init();
for(int i=0;i<n;i++)
{
cin>>s;
//scanf(" %c",&s);//%c前面需要一个空格以吸收上次输入缓冲区中的换行
//下标从2开始,所以第k个插入的数的下标是k+1
if(s=="L")
{
cin>>x;
insert_IR(0,x);
}
else if(s=="R")
{
cin>>x;
insert_IR(l[1],x);
}
else if(s=="D")
{
cin>>k;
Del(k+1);
}
else if(s=="IL")
{
cin>>k>>x;
insert_IR(l[k+1],x);
}
else if(s=="IR")
{
cin>>k>>x;
insert_IR(k+1,x);
}
}
printNode();
return 0;
}