AcWing 827. 双链表(一点即通)
原题链接
简单
作者:
顾龍_
,
2023-12-11 17:49:12
,
所有人可见
,
阅读 56
#include <iostream>
using namespace std;
const int N = 100010;
int m;
int e[N], l[N], r[N], idex;
void init()
{
r[0] = 1, l[1] = 0; //0表示头结点,1表示尾结点
idex = 2;
}
//在下标为k的位置插入一个数
void add(int k,int x)
{
e[idex] = x;
l[idex] = k;
r[idex] = r[k];
l[r[k]] = idex;//此处先进行此操作
r[k] = idex;//再进行此操作
idex++;
}
//删除下标为k的点
void dele(int k)
{
r[l[k]] = r[k];
l[r[k]] = l[k];
}
//一开始头结点始终为0,尾结点始终为1,因为idex从2开始。
//所以第一个插入的数的下标为idex即为2,第2个数插入的下标为3,以此类推,所以第k个插入的数下标就是k+1
//头结点0和尾结点1之间节点的下标是2,3,4,5删除某一个节点后,下标是不连续的。
int main()
{
init();
cin >> m;
string c;
while(m--)
{
int k,x;
cin >> c;
if(c == "L")
{
cin >> x;
add(0,x);
}
else if(c == "R")
{
cin >> x;
add(l[1],x);
}
else if(c == "D")
{
cin >> k;
dele(k + 1);
}
else if(c == "IL")
{
cin >> k >> x;
add(l[k + 1],x);
}
else
{
cin >> k >> x;
add(k + 1,x);
}
}
for(int i = r[0]; i != 1; i = r[i])
cout << e[i] <<" ";
return 0;
}