题目描述
实现一个双链表,双链表初始为空,支持 5 种操作:
- 在最左侧插入一个数;
- 在最右侧插入一个数;
- 将第 k 个插入的数删除;
- 在第 k 个插入的数左侧插入一个数;
- 在第 k 个插入的数右侧插入一个数;
现在要对该链表进行 M 次操作,进行完所有操作后,从左到右输出整个链表。
注意:题目中第 k 个插入的数并不是指当前链表的第 k 个数。例如操作过程中一共插入了 n 个数,则按照插入的时间顺序,这 n 个数依次为:第 1 个插入的数,第 2 个插入的数,…第 n 个插入的数。
输入格式
第一行包含整数 M,表示操作次数。
接下来 M 行,每行包含一个操作命令,操作命令可能为以下几种:
- L x,表示在链表的最左端插入数 x。
- R x,表示在链表的最右端插入数 x。
- D k,表示将第 k 个插入的数删除。
- IL k x,表示在第 k 个插入的数左侧插入一个数。
- IR k x,表示在第 k 个插入的数右侧插入一个数。
输出格式
共一行,将整个链表从左到右输出。
数据范围
41\le M\le 100000$
所有操作保证合法。
输入样例
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
算法思路
一 问题难点
双链表中我jio得比较难的是:
①理解初始空链表时的左右指向
②链表左右端插入问题
③需要考虑好第k个节点的含义,也就是为啥每次的插入(普通插入)和删除需要进行k + 1
二 问题解决过程
进行双链表的初始化
这里用0表示最左端(即head),而用1表示最右端(即tail),因此idx初始为2(表示当前可用的存储结点位置)
理解方法①:初始时双链表中是没有存储结点的,可以理解成一个空指针,但空指针也是要左右指向的(类似单链表中,链表空时,头指针head指向头结点-1),可以用r[]表示右指向,l[]表示左指向,因此r[0] = 1, l[1] = 0, 表示如下:
$$0 \xleftarrow{l[1]} Null \xrightarrow{r[0]} 1(这里的Null可以理解成桥梁作用)$$
理解方法②: 当前链表为空,只有左右端点(左端点0表示head,右端点1表示tail),但要满足双链表的性质,即左端点指向右端点,右端点指向左端点,因此表示如下:
$$0\rightleftarrows1 (其中r[0] = 1, l[1] = 0)$$
插入操作的理解
先理解第k个节点含义:因为节点0和节点1被使用于双链表的head和tail, 因此插入的第一个节点应从idx = 2开始,因此插入时 k + 1,同理删除操作也是这么理解(插入理解是普通插入)
节点的插入函数只要考虑普通右插入即可,针对其他四种插入可进入如下理解:
① (普通插入)第k个节点的左边插入x:insert(L(k + 1), x), 其中l[k + 1]表示当前节点的前一个节点,即前一个节点右插等于当前节点的左插
② (普通插入)第k个节点的右边插入x: insert(k + 1, x)
③ 最左端插入x: insert(0, x),因为最左端节点位置要始终为0,即它的左端不能插值,因此只能进行右插入
④ 最右端插入x: insert(L(1), x),因为最右端节点位置要始终为1,即它的右端不能插值,因此只能进行左插入,即L[1]
普通插入过程:
删除操作的理解
三 案例模拟
四 C++ 代码
#include <iostream>
using namespace std;
const int N = 1e5 + 10;
int val[N], l[N], r[N], idx;
void init(){
// 0表示左端点, 1表示右端点
l[1] = 0, r[0] = 1;
idx = 2;
}
void insert(int k, int x){
val[idx] = x;
r[idx] = r[k];
l[idx] = k;
l[r[k]] = idx;
r[k] = idx;
idx ++;
}
void remove(int k){
r[l[k]] = r[k];
l[r[k]] = l[k];
}
int main(){
int m;
cin >> m;
init();
while (m --){
string op;
int k, x;
cin >> op;
if (op == "R"){
cin >> x;
insert(l[1], x);
}
else if (op == "L"){
cin >> x;
insert(0, x);
}
else if (op == "D"){
cin >> k;
remove(k + 1);
}
else if (op == "IR"){
cin >> k >> x;
insert(k + 1, x);
}
else {
cin >> k >> x;
insert(l[k + 1], x);
}
}
for (int i = r[0]; i != 1; i = r[i]) cout << val[i] << ' ';
return 0;
}