实现一个双链表，双链表初始为空，支持 $5$ 种操作：

1. 在最左侧插入一个数；
2. 在最右侧插入一个数；
3. 将第 $k$ 个插入的数删除；
4. 在第 $k$ 个插入的数左侧插入一个数；
5. 在第 $k$ 个插入的数右侧插入一个数

现在要对该链表进行 $M$ 次操作，进行完所有操作后，从左到右输出整个链表。

注意:题目中第 $k$ 个插入的数并不是指当前链表的第 $k$ 个数。例如操作过程中一共插入了 $n$ 个数，则按照插入的时间顺序，这 $n$ 个数依次为：第 $1$ 个插入的数，第 $2$ 个插入的数，…第 $n$ 个插入的数。

输入格式

第一行包含整数 $M$，表示操作次数。

接下来 $M$ 行，每行包含一个操作命令，操作命令可能为以下几种：

1. L x，表示在链表的最左端插入数 $x$。
2. R x，表示在链表的最右端插入数 $x$。
3. D k，表示将第 $k$ 个插入的数删除。
4. IL k x，表示在第 $k$ 个插入的数左侧插入一个数。
5. IR k x，表示在第 $k$ 个插入的数右侧插入一个数。

输出格式

共一行，将整个链表从左到右输出。

数据范围

$1 \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

已生成可直接用于 OJ 的压缩包，文件名格式是： • 1.in / 1.out • 2.in / 2.out • … • 25.in / 25.out

下载链接： 双链表测试数据 zip

下面按 1~25 说明每组数据分别在卡什么常见错误做法。

⸻

正确做法

这题正确做法是 静态数组模拟双链表，常见写法： • e[idx]：当前节点值 • l[idx]：左指针 • r[idx]：右指针 • 用两个哨兵： • 0 表示左端点 • 1 表示右端点 • 真正插入的第一个节点从 idx = 2 开始

并且要特别注意：

题目里的“第 k 个插入的数”，是 按插入时间编号，不是当前链表里第 k 个位置。

所以如果你内部节点下标从 2 开始，那么： • 第 k 个插入的数，对应节点编号是 k + 1

常见操作可统一成： • L x：插到左哨兵 0 的右边 • R x：插到右哨兵 1 的左边 • D k：删掉编号 k+1 • IL k x：插到编号 k+1 的左边 • IR k x：插到编号 k+1 的右边

⸻

25 组数据分别卡什么

1

样例 卡基础正确性，综合覆盖： • 左插 • 右插 • 删除指定编号 • 在指定编号左侧插入 • 在指定编号右侧插入

⸻

2

单次左插 卡： • 初始化 • 空链表转非空链表 • 最终输出一个元素

⸻

3

单次右插 卡： • 右端插入 • 哨兵右边界维护

⸻

4

先左插后右插 卡： • 左右端混合插入的顺序

⸻

5

删除唯一节点 卡： • 删除后链表重新变空 • 左右哨兵重新相连

⸻

6

连续左插 卡： • 左插顺序应该是逆序 • 很多人会写成尾插效果

⸻

7

连续右插 卡： • 右插顺序应该保持插入顺序

⸻

8

在第 1 个插入节点左侧插入 卡： • IL k x 是按插入编号找节点 • 不是当前链表第 k 个位置

⸻

9

在第 1 个插入节点右侧插入 卡： • IR k x 的定位逻辑 • 很多人会误把它写成“插在第 k 个位置后”

⸻

10

连续在同一节点左插 卡： • 同一个节点左侧连续插入时，局部顺序变化 • 新插入节点会更靠近该节点

⸻

11

连续在同一节点右插 卡： • 同一个节点右侧连续插入时的局部顺序 • 容易把链接方向写错

⸻

12

删除中间节点 卡： • 双链表删除时必须同时维护 l 和 r • 单改一个方向会断链

⸻

13

删除第 1 个插入节点，但它不在最左 卡： • “第 k 个插入”不等于当前位置 • 很多错误做法会删错位置

⸻

14

删除最后插入节点，但它不在最右 卡： • 插入顺序编号和当前位置无关 • 删除逻辑不能靠“当前最右”猜

⸻

15

值包含 0 和负数 卡： • 错误地把节点值当数组下标 • 错误假设值全为正

⸻

16

交替多种操作 卡： • 左插 / 右插 / 左侧插入 / 右侧插入 / 删除 混合使用 • 状态维护容易乱

⸻

17

专卡“把第 k 个插入误认为当前第 k 个节点” 这类错误代码在这组一定会错。

⸻

18

节点邻接关系多次变化后删除 卡： • 删除的是编号节点本身，不是某个固定位置 • 多次插入后左右邻居会变

⸻

19

中小规模综合 卡： • 多次引用早期编号 • 删除后再继续在旧编号附近插入 • 状态连续变化

⸻

20

10^5 次全左插 卡： • 性能 • 输出顺序 • O(M²) 做法会炸

⸻

21

10^5 次全右插 卡： • 性能 • 尾部维护 • 输出顺序

⸻

22

10^5 次都在第 1 个插入节点左侧插入 卡： • 按插入编号定位 • 同一节点左边反复插入的局部顺序 • 很多人会把 IL 写错成头插

⸻

23

10^5 次都在第 1 个插入节点右侧插入 卡： • 按插入编号定位 • 同一节点右边反复插入的局部顺序 • 很多人会把 IR 写错成尾插

⸻

24

大规模左右交替插入 卡： • 左右哨兵同时维护 • 双端插入性能 • 如果指针更新顺序错，很容易断链

⸻

25

综合大规模：围绕早期编号大量左右插，再删除大量旧编号 卡： • 频繁引用很早插入的节点 • 节点已经不是原来位置 • 删除大量旧编号 • 性能与双向指针维护都容易出错

⸻

如果你愿意，我下一条还可以继续给你补这题的：

最常见错误代码总结，比如： • 为什么 D k 要删 k+1 • 为什么必须用左右哨兵 • 为什么 IL / IR 最好统一成一个 insert_right() 模板来写