AcWing 827. 双链表
原题链接
简单
作者:
冉俊泽
,
2022-02-22 15:40:11
,
所有人可见
,
阅读 203
#include<iostream>
#include<string>
using namespace std;
//e[]存放数据,nel[i]表示i的指向前驱,ner[i]表示指向i的后驱
//idx表示现在可用的节点,head表示头节点,rear表示尾节点
const int N = 100010;
int e[N],nel[N],ner[N];
int idx;
//初始化双链表
void init()
{
nel[1] = 0;//0表示左端点
ner[0] = 1;//1表示右端点
idx = 2;
}
//将第K个插入的数删除
void remove(int k)
{
nel[ner[k]] = nel[k];
ner[nel[k]] = ner[k];
}
//在第k个插入的数右侧插入一个数
void add(int k, int x)
{
e[idx] = x;
nel[idx] = k;
ner[idx] = ner[k];
nel[ner[k]] = idx;
ner[k] = idx;
idx++;
}
int main()
{
init();
int m;
cin >> m;
while (m--)
{
int k, x;
string op;
cin >> op;
if( op == "L")
{
cin >> x;
add(0, x);//在做左端点插入x
}
else if( op == "R")
{
cin >> x;
add(nel[1], x);//在右端点插入x
}
else if(op == "D")
{
cin >> k;
remove(k + 1);
}
else if(op == "IL")
{
//在第k个插入的数左侧插入一个数
cin >> k >> x;
add(nel[k + 1], x);
}
else
{
//在第K个插入的数右侧插入一个数
cin >> k >> x;
add(k + 1, x);
}
}
//输出链表元素
for(int i = ner[0]; i != 1; i = ner[i]) cout << e[i] << " ";
cout << endl;
return 0;
}