AcWing 827. 双链表
原题链接
简单
作者:
._5144
,
2023-11-17 18:45:02
,
所有人可见
,
阅读 55
#include <iostream>
using namespace std;
const int N = 1e5 + 10;
int m;
int l[N],r[N],e[N],idx;
void init()
{
r[0] = 1; // 0号节点为头节点
l[1] = 0; // 1号节点为尾节点
// 此时的0和1其实只是表示头节点和尾节点,并没有实际意义
idx = 2; // 此时已经用掉两个节点
// 因为idx从2开始,所以第k个节点的下标就是k + 1
}
// 在下标为k的节点右侧插入x
// 该题目中的四个插入方式,这一个函数即可完成
// 在最左侧插入一个数时,就相当于在0号位置的右侧插入,此时头节点就为新插入的节点
// 在最右侧插入一个数时,就相当于在指向1号节点的右侧插入,此时的l[1]指向的就是插入的节点,并且该节点就为尾节点
// 在下标为k的节点左侧插入x等价于在下标为k的节点左侧的右侧插入x
// 故也可以直接调用addR(l[k],x);
void addR(int k, int x)
{
e[idx] = x;
r[idx] = r[k];
l[r[k]] = idx;
r[k] = idx;
l[idx] = k;
idx ++;
}
// // 在下标为k的节点左侧插入x
// void addL(int k, int x)
// {
// e[idx] = x;
// l[idx] = l[k];
// r[idx] = k;
// r[l[k]] = idx;
// l[k] = idx;
// idx ++;
// }
// 在下标为k的节点左侧插入x等价于在下标为k的节点左侧的右侧插入x
// 故也可以直接调用addR(l[k],x);
// 删除下标为k的节点
void remove(int k)
{
r[l[k]] = r[k];
l[r[k]] = l[k];
}
int main()
{
init();
cin >> m;
while(m --)
{
int k,x;
string op;
cin >> op;
if(op == "L")
{
cin >> x;
addR(0,x);
}
else if(op == "R")
{
cin >> x;
addR(l[1],x);
}
else if(op == "D")
{
cin >> k;
remove(k + 1); // 第k个节点的下标其实为k+1
}
else if(op == "IL")
{
cin >> k >> x;
addR(l[k + 1],x);
}
else
{
cin >> k >> x;
addR(k + 1, x);
}
}
for(int i = r[0]; i != 1; i = r[i]) cout << e[i] << ' ';
cout << endl;
return 0;
}