SZTG-L-B4324. 【模板】双向链表
题目描述
【模板】双向链表
题目描述
给出 个结点，编号依次为 ，初始按编号从小到大排列成一条双向链表。
接下来有 条指令，请按要求对链表进行修改。所有操作均保证合法。
| 指令 | 含义 |
|---|---|
| 将结点 插入到 的左侧（若 则忽略本条指令）。 | |
| 将结点 插入到 的右侧（若 则忽略本条指令）。 | |
| 删除结点 ；若 已被删除则忽略本条指令。 |
操作结束后，请按从左到右的顺序输出当前链表中所有结点的编号。
输入格式
第一行输入两个正整数 ，表示链表初始的结点数和操作指令数。
接下来 行，每行一条指令，如题意所述。
输出格式
输出一行，即：操作结束后，按从左到右的顺序输出当前链表中所有结点的编号。如果链表不存在结点，输出 Empty!。
输入样例 #1
10 7
1 2 3
2 4 5
3 2
1 9 4
2 7 8
3 4
3 10
输出样例 #1
1 3 5 9 6 8 7
说明/提示
样例解释
- 初始时，链表为：；
- 第一次操作，将 插入到 左侧。由于初始时已经符合 在 左侧，所以链表还是：；
- 第二次操作，将 插入到 的右侧，链表为：；
- 第三次操作，删除结点 ，链表为：；
- 第四次操作，将 插入到 的左侧，链表为：；
- 第五次操作，将 插入到 的右侧，链表为：；
- 第六次操作，删除结点 ，链表为：；
- 第七次操作，删除结点 ，链表为：；
输入样例 #2
12 21
2 12 6
2 1 12
1 11 4
2 7 9
2 11 10
3 7
3 2
2 4 5
1 9 5
2 12 5
2 12 1
2 12 4
2 5 6
2 12 9
2 10 5
3 10
2 9 6
2 4 9
2 11 8
3 11
3 5
输出样例 #2
3 12 6 9 4 1 8
输入样例 #3
14 22
3 5
1 7 6
3 11
2 6 12
2 7 2
2 9 1
2 7 3
3 13
2 3 10
2 10 9
1 10 9
1 6 4
3 10
1 14 3
1 6 8
3 3
3 9
2 2 4
1 6 8
2 8 4
2 2 8
1 4 1
输出样例 #3
4 1 7 8 2 6 14 12
数据范围
- 对于 的数据，；
- 对于 的数据，；
- 对于所有数据，；