题目描述
实现一个双链表,双链表初始为空,支持5种操作:
(1) 在最左侧插入一个数;
(2) 在最右侧插入一个数;
(3) 将第k个插入的数删除;
(4) 在第k个插入的数左侧插入一个数;
(5) 在第k个插入的数右侧插入一个数
现在要对该链表进行M次操作,进行完所有操作后,从左到右输出整个链表。
输入
10
R 7
D 1
L 3
IL 2 10
D 3
IL 2 7
L 8
R 9
IL 4 7
IR 2 2
输出
8 7 7 3 2 9
#include<iostream>
using namespace std;
const int N = 100010;
int m;
int e[N], l[N], r[N], idx;
//在a的右边插入一个数
void insert(int a, int x){
e[idx] = x;
l[idx] = a, r[idx] = r[a];
l[r[a]] = idx, r[a] = idx ++;
}
void remove(int x){
l[r[x]] = l[x];
r[l[x]] = r[x];
}
int main(){
//0是左端点,1是右端点
r[0] = 1, l[1] = 0;
idx = 2; //idx从2开始所以第k个点下标为k + 1
cin >> m;
while(m --){
string op;
cin >> op;
int k, x;
if (op == "L")
{
cin >> x;
insert(0, x);
}
else if (op == "R")
{
cin >> x;
insert(l[1], x);
}
else if (op == "D")
{
cin >> k;
remove(k + 1);
}
else if (op == "IL")
{
cin >> k >> x;
insert(l[k + 1], x);
}
else
{
cin >> k >> x;
insert(k + 1, x);
}
}
for(int i = r[0]; i != 1; i = r[i]) cout << e[i] << " ";
puts("");
return 0;
}