204.单链表

# 单链表

## 题目描述

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

1. 向链表头部插入一个整数。
2. 删除第 $k$ 个插入的节点的后继节点。
3. 在第 $k$ 个插入的节点后插入一个整数。

现在需要对该链表进行 $M$ 次操作。完成所有操作后，按从头到尾的顺序输出链表中各节点的值。

**注意：**第 $k$ 个插入的节点不是指当前链表中的第 $k$ 个节点。所有插入操作（包括头部插入和在指定节点后插入）按执行时间依次编号，编号从 $1$ 开始。节点被删除后，其编号不会被重新使用，其他节点的编号也不会改变。

## 输入格式

从文件 `list.in` 中读入数据。

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

接下来 $M$ 行，每行包含一个操作命令，格式为以下三种之一：

- `H x`：向链表头部插入一个值为 $x$ 的节点。
- `D k`：当 $k>0$ 时，删除第 $k$ 个插入的节点的后继节点；当 $k=0$ 时，删除头节点。
- `I k x`：在第 $k$ 个插入的节点后插入一个值为 $x$ 的节点，其中 $k>0$。

## 输出格式

将结果输出到文件 `list.out` 中。

输出一行，按从头到尾的顺序输出链表中各节点的值，相邻两个值之间用一个空格分隔。

若最终链表为空，则输出一个空行。

## 数据范围

- $1 \le M \le 100000$。
- $x$ 是 `int` 类型的整数。
- 所有操作保证合法：操作中引用的节点以及待删除的节点均存在。

## 样例输入

```
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
```

## 样例说明

下表中的链表状态按从头到尾的顺序列出节点值：

| 操作 | 操作后的链表 |
| --- | --- |
| `H 9` | $9$ |
| `I 1 1` | $9 \to 1$ |
| `D 1` | $9$ |
| `D 0` | 空链表 |
| `H 6` | $6$ |
| `I 3 6` | $6 \to 6$ |
| `I 4 5` | $6 \to 6 \to 5$ |
| `I 4 5` | $6 \to 6 \to 5 \to 5$ |
| `I 3 4` | $6 \to 4 \to 6 \to 5 \to 5$ |
| `D 6` | $6 \to 4 \to 6 \to 5$ |

最后一次操作删除的是第 $6$ 个插入的节点的后继，即第 $5$ 个插入的节点。

## 运行限制

- 时间限制：$1000$ 毫秒。
- 内存限制：$64$ MB。