HM215 链式节点

来源： 第 215 集 list容器-基本概念

难度： 普及-

时间限制： 1s

空间限制： 64MB

题目描述

链表由一个个**节点**串起来。每个节点有数据域；节点之间靠指针相连，物理地址**不连续**。因此迭代器只能一步一步 ++ / --，不能按下标跳跃，也不能用 []。

和连续数组相比：

• 在偏移 \(p\) 插入时，链表只需改指针，**不必把后面的元素搬家**；
• 同样位置若是连续数组，后面的 \(\textit{size}-p\) 个元素都要后移。

STL 的 list 是双向循环链表，还支持头尾插删。插入、删除一般**不会**让指向其他节点的迭代器失效（被删掉的那个除外）。空间按节点按需分配，有几个元素就有几个节点，不会像动态数组那样额外留一大段容量。

本题用链表完成一次「先做书签、再插入」：

1. 默认构造空链表，把输入序列依次尾插。
2. 迭代器从 begin() 出发，只做 \(b\) 次 ++，记下这本书签（指向插入前的第 \(b\) 个节点，从 \(0\) 数）。
3. 再从 begin() 出发只做 \(p\) 次 ++，在该处插入 \(x\)。
4. 正向打印整条链表。
5. 输出：若这是连续数组，这次插入需要移动多少个元素。
6. 从 end() 连续 --，反向打印整条链表。
7. 输出书签解引用的值，用来确认插入没有让它失效。

禁止使用 []、at 或迭代器加法。保证链表插入前非空，书签和插入位置合法，且不会删除书签节点。

输入格式

第一行一个整数 \(n\)（\(n \ge 1\)）。

第二行 \(n\) 个整数，依次尾插。

第三行一个整数 \(b\)，表示书签偏移。

第四行两个整数 \(p\)、\(x\)，表示在偏移 \(p\) 插入 \(x\)。

输出格式

共四行：

1. 插入后的正向序列，空格分隔，行末无多余空格；
2. 一个整数：连续数组在该位置插入时要移动的元素个数；
3. 插入后的反向序列，空格分隔，行末无多余空格；
4. 书签仍指向的那个整数。

样例

输入 #1

4
10 20 30 40
1
1 100

输出 #1

10 100 20 30 40
3
40 30 20 100 10
20

输入 #2

3
1 2 3
0
3 9

输出 #2

1 2 3 9
0
9 3 2 1
1

说明

\(1 \le n \le 1000\)，\(0 \le b < n\)，\(0 \le p \le n\)，元素与 \(x\) 的绝对值不超过 \(10^9\)。

样例 #1：在 \(10\) 和 \(20\) 之间插入 \(100\)。连续数组要把后面 \(3\) 个数后移；链表只改指针。书签原来指着 \(20\)，插入后仍然是 \(20\)。样例 #2 在末尾插入，数组不用搬家。