单链表
第一行包含整数M,表示操作次数。
接下来M行,每行包含一个操作命令,操作命令可能为以下几种:
(1) “H x”,表示向链表头插入一个数x。
(2) “D k”,表示删除第k个插入的数后面的数(当k为0时,表示删除头结点)。
(3) “I k x”,表示在第k个插入的数后面插入一个数x(此操作中k均大于0)。
输入样例
10
H 9
I 1 1
D 1
D 0
H 6
I 3 6
I 4 5
I 4 5
I 3 4
D 6
输出样例
6 4 6 5
代码
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1e5 + 10;
int e[N], ne[N], head, idx;//数值 下一个指针 头指针 当前位置
void init()//初始化
{
idx = 0;
head = -1;
}
void add_to_head(int x)//将x插入头结点
{
e[idx] = x;
ne[idx] = head;
head = idx;
idx++;
}
void add(int k, int x)//在第k个插入的数后面插入一个数x
{
e[idx] = x;
ne[idx] = ne[k];
ne[k] = idx;
idx++;
}
void remove(int k)//删除第k个插入的数后面的数
{
ne[k] = ne[ne[k]];
}
int main()
{
int n;
cin >> n;
init();
while (n--)
{
char c;
int k, x;
cin >> c;
if (c == 'H')
{
cin >> x;
add_to_head(x);
}
else if (c == 'D')
{
cin >> k;
if (k == 0)//当k=0时,删去头节点
head = ne[head];
else
remove(k - 1);
}
else
{
cin >> k >> x;
add(k-1, x);
}
}
for (int i = head; i != -1; i = ne[i])
cout << e[i] << ' ';
return 0;
}