题面:实现一个双链表,双链表初始为空,支持 5 种操作:
- 在最左侧插入一个数;
- 在最右侧插入一个数;
- 将第 k 个插入的数删除;
- 在第 k 个插入的数左侧插入一个数;
- 在第 k 个插入的数右侧插入一个数
现在要对该链表进行 M 次操作,进行完所有操作后,从左到右输出整个链表。
原题链接:827. 双链表 - AcWing
#include<bits/stdc++.h>
using namespace std;
const int N = 100005;
int e[N], l[N], r[N], cnt;
void init() {
l[1] = 0;
r[0] = 1;
cnt = 2;
}
//在第k个点后插入一个数字x
//若要实现在第k点前,k的输入为k的左侧即l[k]即可
void add(int k, int x) {
e[cnt] = x;
//先连接新节点
l[cnt] = k; //x的左侧为k
r[cnt] = r[k]; //x的右侧 为 原本k的右侧结点
//再断掉旧结点链接
l[r[k]] = cnt; //x,即原本k的右侧结点的现在左侧
r[k] = cnt++; //原本k的右侧结点更新为x,x更新
}
void deleteK(int k) {
//不能使用l[k] = r[k],左右指针数组不互通
r[l[k]] = r[k];
l[r[k]] = l[k];
}
void printList() {
for (int i = r[0]; i != 1; i = r[i])
cout << e[i] << " ";
cout << endl;
}
int main()
{
int m;
cin >> m;
init();
while (m--) {
string op;
int k, x;
cin >> op;
if (op == "L") {
cin >> x;
add(0, x); //首结点后
}
else if (op == "R") {
cin >> x;
add(l[1], x); //右边界的左节点后
}
else if (op == "D") {
cin >> k;
deleteK(k + 1); //首先插入的是索引分别为0和1的头尾结点
}
else if (op == "IL") {
cin >> k >> x;
add(l[k + 1], x);
}
else {
cin >> k >> x;
add(k + 1, x);
}
}
printList();
return 0;
}