AcWing 827. 双链表
原题链接
简单
作者:
PeterYan
,
2024-01-09 20:27:32
,
所有人可见
,
阅读 44
#include <iostream>
#include <string>
using namespace std;
const int N = 1e5 + 10;
int e[N], l[N], r[N], idx;
//初始化
void init()
{
r[0] = 1;
l[1] = 0;
idx = 2;
}
//在k的右侧插入一个元素;在k的左侧加入一个元素的代码:add(l[k], x);
void add(int k, int x)
{
e[idx] = x;
l[idx] = k;
r[idx] = r[k];
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()
{
init();
int m, k, x;
cin >> m;
while(m--)
{
string op;
cin >> op;
if(op == "L")
{
cin >> x;
add(0, x);
}
else if(op == "R")
{
cin >> x;
add(l[1], x);
}
else if(op == "IL")
{
cin >> k >> x;
add(l[k + 1], x);
}
else if(op == "IR")
{
cin >> k >> x;
add(k + 1, x);
}
else if(op == "D")
{
cin >> k;
remove(k + 1);
}
}
int pos = r[0];
while (pos != 1)
{
cout << e[pos] << ' ';
pos = r[pos];
}
cout << endl;
return 0;
}