实现一个单链表，链表初始为空，支持三种操作：

1. 向链表头插入一个数；
2. 删除第 $k$ 个插入的数后面的一个数；
3. 在第 $k$ 个插入的数后插入一个数。

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

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

输入格式

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

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

1. H x，表示向链表头插入一个数 $x$。
2. D k，表示删除第 $k$ 个插入的数后面的数（当 $k$ 为 $0$ 时，表示删除头结点）。
3. I k x，表示在第 $k$ 个插入的数后面插入一个数 $x$（此操作中 $k$ 均大于 $0$）。

输出格式

共一行，将整个链表从头到尾输出。

数据范围

$1 \le M \le 100000$
所有操作保证合法。

输入样例：

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

已生成可直接用于 OJ 的测试数据压缩包，命名方式为： • 1.in / 1.out • 2.in / 2.out • … • 25.in / 25.out

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

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

⸻

正确做法

这题正确做法是 静态数组模拟单链表： • e[idx] 存当前节点的值 • ne[idx] 存当前节点的后继下标 • head 存头结点下标 • idx 表示当前新插入节点编号

关键理解： • 题目里的“第 k 个插入的数” 指的是 插入顺序编号 • 不是当前链表中的第 k 个位置

所以： • H x：新建节点，头插 • I k x：在编号 k-1 的节点后插入（如果你内部从 0 开始存） • D 0：删头 • D k：删“第 k 个插入节点”的后一个节点

⸻

25 组数据分别卡什么

1

样例 卡基础正确性，覆盖： • 头插 • 指定节点后插入 • 删除头结点 • 删除某插入节点的后继

⸻

2

只有一次头插 卡： • 初始化是否正确 • 只有一个结点时是否能正常输出

⸻

3

连续头插后删除头 卡： • D 0 的特殊处理 • 是否正确更新 head

⸻

4

对同一个插入编号先插后删 卡： • “第 k 个插入的数”不是当前位置 • 删除的是它当前后继，而不是“最初后继”

⸻

5

连续头插 卡： • 头插的最终顺序应该是逆序 • 很多人会误写成尾插效果

⸻

6

在旧节点后插入 卡： • 按插入编号定位节点 • 错误做法会把 k 当成当前链表位置

⸻

7

删除第 1 个插入节点后继 卡： • 插入顺序编号和链表中位置不同 • 删除逻辑是否真按“编号节点”删除后继

⸻

8

连续在同一节点后插入 卡： • 后插多次时，后插入的点会更靠前 • 很多人会误以为顺序保持插入顺序

例如： I 1 8, I 1 9, I 1 10 最终局部顺序应是： 1 -> 10 -> 9 -> 8

⸻

9

多次删除头 卡： • 连续 D 0 • head 是否一直正确向后移动

⸻

10

在最新插入编号后继续插入 卡： • idx 和“第 k 个插入”映射是否正确 • 是否能正确引用新插入的编号

⸻

11

值包含 0 和负数 卡： • 误把值当数组下标 • 错误假设值一定为正

⸻

12

删除尾节点 卡： • 删除某节点后继时，如果后继本来就是尾结点 • 是否能正确把 ne[p] 置为 -1

⸻

13

交替头插 / 后插 / 删除 卡： • 状态维护是否混乱 • 多种操作混用时链表是否断掉

⸻

14

围绕同几个编号反复操作 卡： • 后继关系不断变化时是否仍能正确定位 • 不是“固定后继”，而是“当前后继”

⸻

15

专门卡“把 k 当当前第 k 个节点” 卡： • 题意理解错误 • 这类错法在这组一定会错

⸻

16

删除某编号节点当前后继，而不是原始后继 卡： • 很多人误以为“第 k 个插入节点的后继”是固定的 • 实际上链表结构在动态变化

⸻

17

中小规模综合 卡： • 多层插入 • 多次删除 • 引用早期节点和新节点混合出现

⸻

18

只有 insert-after 形成长链 卡： • 连续在前一个插入节点后插入 • 是否能正确形成长链 • 遍历输出是否正确

⸻

19

连续删除中间结点后继 卡： • 删除中间链路时，是否正确跳过节点 • 容易出现断链或删错点

⸻

20

10^5 次全头插 卡： • 性能 • 头插顺序 • 输出是否会超时 • 暴力链表 / STL list 写法一般也能过，但数组模拟最稳

⸻

21

10^5 次都在第 1 个插入节点后插入 卡： • “同一节点后反复插入”的局部逆序特性 • 如果理解错，顺序会完全反

⸻

22

大规模：先构长链，再大量删头 卡： • 大量操作的性能 • head 连续更新 • 删除后遍历是否稳定

⸻

23

大规模交替：头插 + 在第 1 个插入节点后插 卡： • 插入编号不随链表位置变化 • 早期编号节点始终还能被引用 • 很卡题意理解

⸻

24

大量在同一节点后插入，再大量删除该节点后继 卡： • 同一节点后继不断变化 • 删除逻辑是否始终删除“当前后继” • 很容易写错成删除固定节点

⸻

25

综合手造大坑 卡： • 多次引用早期编号 • 删除头 • 删除变化后的后继 • 在删除之后继续引用旧编号 • 很多实现细节错法会在这一组翻车

⸻

如果你要，我下一条可以继续直接给你补一份：

这题最常见的错误代码写法总结 比如： • 为什么 D k 要写成删 ne[k] • 为什么 I k x 不是插到第 k 个位置后 • 为什么数组下标和插入编号要错开 1

我可以直接按“会错在哪 + 正确写法”给你列出来。