第 31 章 链表¶
配套例题：BISHI1 【模板】序列操作（题解已通过官方样例）、BISHI96 先序遍历、中序遍历和后序遍历 来源：S2
1-Linear List/Singly Linked List.cpp；S3 day2《链表 DLX 并查集》 前置：30-序列与数组
链表在 C/C++ 里是必修课，在 Python 里却是最容易被误用的数据结构——
因为 Python 没有指针，手写 Node 类的常数大到几乎不可能通过任何 \(10^5\) 级别的题。
这一章的目标不是教你写 class Node，而是让你能回答两个问题：
什么时候真的需要链表？以及在 Python 里应该用什么形式实现它？
31.1 链表的四种形态¶
| 形态 | 每个节点存 | 支持的操作 |
|---|---|---|
| 单向链表 | data、nxt |
已知前驱时 \(O(1)\) 插入/删除，只能单向走 |
| 双向链表 | data、pre、nxt |
已知节点本身即可 \(O(1)\) 删除，双向走 |
| 循环链表 | 首尾相接 | 从任意元素出发可遍历全部（约瑟夫问题） |
| 十字链表 | 同时属于横、竖两条双向循环链表 | 稀疏矩阵、Dancing Links |
S2 的 Singly Linked List.cpp 是标准的带头结点单链表：h 是哑结点（哨兵），
真正的第一个元素是 h->next。带头结点的好处是插入删除不需要特判空表。
链表和数组的本质取舍只有一句话：
数组（list） |
链表 | |
|---|---|---|
| 按下标访问第 \(k\) 个 | \(O(1)\) | \(O(k)\) |
| 已知位置后插入/删除 | \(O(n)\)（要搬移） | \(O(1)\) |
| 内存 | 连续，缓存友好 | 分散，每节点多存 1–2 个指针 |
S3 day2 的原话：「如果没有辅助数组，链表无法快速访问内部元素。」 这正是链表的死穴——你必须先有一个指向目标节点的引用， 而拿到这个引用本身往往就要 \(O(n)\)。
31.2 Python 里的三种实现，以及唯一推荐的那种¶
写法 A：class Node（教学用，竞赛禁用）¶
class Node:
__slots__ = ("val", "nxt") # 禁掉每实例的 __dict__，省约 40% 内存
def __init__(self, val, nxt=None):
self.val = val # 数据域
self.nxt = nxt # 指向后继节点，None 表示链尾
每个节点是一个独立的 Python 对象，\(10^5\) 个节点意味着 \(10^5\) 次对象分配，
外加每次 p.nxt 都是一次属性查找（走 __slots__ 描述符）。
实测比数组模拟慢 5–10 倍，且内存翻好几倍。
结论：
class Node只在面试白板题和 LeetCode 给定链表结构时用。 牛客/OI 风格的题一律不要用。
写法 B：数组模拟链表（竞赛标准写法）¶
不建对象，用两个（或三个）整型数组表示指针。「指针」就是下标，0 或 -1 表示空。
# 数组模拟双向链表：编号 1..n，0 号当哨兵（既是头也是尾）
nxt = list(range(1, n + 2)) # nxt[i] = i 的后继，初值恰好是 i + 1
pre = list(range(-1, n + 1)) # pre[i] = i 的前驱，pre[0] = -1 表示头前无人
val = [0] * (n + 2) # 数据域另开一个数组；多开 2 格让下标直接当编号用
所有指针操作变成整数数组读写，全部在 C 层，常数极小。
写法 C：直接用 list / deque（能用就用）¶
大多数「看起来像链表」的题，其实用 list 或 deque 就够了。
先问一句：我真的需要在中间 \(O(1)\) 删除吗？ 如果不需要，别写链表。
31.3 模板：数组模拟双向链表¶
这是本章最重要的模板。竞赛里 95% 的链表需求都可以由它满足。
class ArrayLinkedList:
"""数组模拟的双向循环链表，节点编号 1..n，0 号为哨兵头尾。
所有操作 O(1)，兼容 Python 3.9。
典型用途：需要按任意顺序删除元素，同时保持「剩余元素的前后关系」。
"""
def __init__(self, n):
# 初始链表顺序为 0 -> 1 -> 2 -> ... -> n -> 0（环）
self.nxt = list(range(1, n + 2)) # 下标 0..n，初值 nxt[i] = i + 1
self.nxt[n] = 0 # 末尾指回哨兵，成环后遍历不必单独判尾
self.pre = [n] + list(range(0, n)) # pre[0] = n 把哨兵前驱接到末尾，其余 pre[i] = i-1
# alive 只做逻辑删除标记；bytearray 每格 1 字节，比布尔列表省 8 倍内存
self.alive = bytearray([1]) * (n + 1)
self.alive[0] = 1 # 哨兵永不删除，它是遍历与插入的固定入口
self.size = n # 只数真实节点，哨兵不计入
def remove(self, x):
"""删除节点 x，O(1)。"""
p, q = self.pre[x], self.nxt[x] # 取出左右邻居；x 自己的两个指针字段保持不动
self.nxt[p] = q # 左邻居越过 x，直接指向右邻居
self.pre[q] = p # 右邻居的前驱回指左邻居，两侧同步才不会断链
self.alive[x] = 0 # 逻辑删除标记，供外部判断 x 是否还在链上
self.size -= 1 # 计数同步，判空判满都看它
def insert_after(self, x, y):
"""把节点 y 插到 x 之后，O(1)。"""
q = self.nxt[x] # 先存下 x 原来的后继，下一行就会覆盖它
self.nxt[x] = y # x 的后继改成 y
self.pre[y] = x # y 的前驱是 x
self.nxt[y] = q # y 的后继是 x 原来的后继
self.pre[q] = y # 原后继的前驱改成 y；四条赋值少一条就断链
self.alive[y] = 1 # y 重新上链
self.size += 1 # 计数同步
def restore(self, x):
"""撤销一次 remove(x)（DLX 的核心技巧），O(1)。
前提：x 被删除后，x 的 pre/nxt 字段没有被修改过。
"""
# 多次删除要按删除的逆序撤销，否则被后来者覆盖过的指针恢复不回来
p, q = self.pre[x], self.nxt[x] # x 仍记得当初站在谁和谁中间，直接复用
self.nxt[p] = x # 左邻居重新指向 x
self.pre[q] = x # 右邻居重新指回 x，删除即被撤销
self.alive[x] = 1 # 标记复位
self.size += 1 # 计数复位
def traverse(self):
"""从哨兵出发按当前顺序遍历，O(size)。"""
res = []
i = self.nxt[0] # 从哨兵的后继起步，哨兵本身不是元素
while i != 0: # 绕回 0 号说明整圈走完，这是环的终止条件
res.append(i)
i = self.nxt[i] # 只跟着 nxt 走，被删的节点已不在链上
return res
restore 为什么能工作¶
S3 day2 讲 Dancing Links 时点破了这个技巧：
回忆循环链表的删除操作。如果保留
x->pre和x->nxt的值不变， 那么可以通过x->pre->nxt = x; x->nxt->pre = x;把x还原到链表中。
也就是说，被删除的节点自己还记得原来站在哪两个人中间。 这让「删除—递归—撤销」变成 \(O(1)\)，是 DLX 求解精确覆盖的基础， 详见 115-高级搜索与精确覆盖。
31.4 经典应用一：约瑟夫问题¶
\(n\) 个人围成一圈，从第 1 个人开始报数 \(1, 2, 3, \dots\)， 数到 \(m\) 的人出列，然后从下一个人重新从 1 开始报。依次输出出列的编号。
解法 1：循环链表模拟，\(O(nm)\)¶
数据范围小（S3 day2 的原题是 \(n, m \le 100\)）时直接模拟：
def josephus_sim(n, m):
nxt = list(range(1, n + 1)) + [0] # 环形后继表：nxt[i] = i + 1，末项指回 0
order = [] # 按出列先后记录编号
pre = n - 1 # cur 的前驱，删除 cur 时要靠它接线
cur = 0 # 从 0 号（即第 1 个人）开始报数
for _ in range(n): # 每轮恰好出列一人，共 n 轮
for _ in range(m - 1): # cur 已经报了 1，再走 m-1 步才数到 m
pre, cur = cur, nxt[cur] # 同步右移，pre 始终紧跟在 cur 前面
order.append(cur + 1) # 内部 0-indexed，题目编号从 1 起，输出前 +1
nxt[pre] = cur = nxt[cur] # 前驱跨过 cur 完成删除，同时 cur 前进到下一人
return order
复杂度 \(O(nm)\)，\(n, m \le 100\) 时是 \(10^4\)，随便过。 但 \(n = 10^5, m = 10^9\) 就完全不可行。
解法 2：只要最后一个幸存者，\(O(n)\) 递推¶
设 \(J(n, m)\) 是 \(n\) 个人时幸存者的0-indexed 编号，则
def josephus_last(n, m):
r = 0 # 边界：只剩 1 个人时，幸存者的 0-indexed 编号就是 0
# i 是当前圈里的人数；人数由 i-1 涨到 i 时，起点相当于把原答案整体后移 m 位
for i in range(2, n + 1):
r = (r + m) % i # 取模把越出圈的位置绕回来，这就是递推式的全部内容
return r + 1 # 转回 1-indexed
\(O(n)\)，且不用任何数据结构。
教训：链表模拟是通解，递推是特解。 竞赛中先看数据范围：\(n \le 10^4\) 就模拟，\(n \le 10^7\) 就找递推。 在 Python 里这条界还要再降一个数量级。
解法 3：树状数组上二分，\(O(n \log n)\)¶
需要输出完整出列顺序且 \(n\) 很大时，用树状数组维护「还剩哪些人」， 每次在树状数组上二分找第 \(k\) 个存活者。见 39-树状数组与线段树。
31.5 经典应用二：需要「\(O(1)\) 任意删除」的题¶
这才是链表在竞赛中真正不可替代的场景。识别特征：
元素只删不加，且删除时你已经知道要删谁（不需要查找）。
典型题型：
| 题型 | 做法 |
|---|---|
| 按某种顺序依次删除元素，每次要知道左右邻居 | 数组模拟双向链表 |
| 「删除后合并相邻元素」的贪心 | 链表 + 堆（堆里存邻居对，懒删除） |
| 倒序处理「删点」问题 | 反过来变成「加点」，用并查集 |
最后一条特别重要，S3 day2 明确点出：
删除不好处理，倒过来变成添加，就变成并查集的拿手好戏了。
所以看到「依次删除若干元素，每次问连通性/集合大小」， 标准套路是离线倒序 + 并查集，而不是链表。见 38-并查集。
「链表 + 堆」的懒删除套路¶
import heapq
# 场景：每次取出「相邻两数之和最小」的一对合并，合并后左右邻居变化
h = [] # 元素是 (代价, 左端点, 版本号)，堆按元组首项排序
ver = [0] * (n + 2) # 版本号：位置每被改一次就加一，旧条目随即作废
lst = ArrayLinkedList(n) # 链表负责回答「合并之后谁挨着谁」
while h:
cost, i, v = heapq.heappop(h) # 取出当前代价最小的候选
if ver[i] != v or not lst.alive[i]: # 版本对不上或节点已下链，说明这是旧快照
continue # 懒删除：堆里删不掉，只能弹出时识别并丢弃
... # 真正处理，更新链表与堆
要点：堆里的条目不能真删，只能靠版本号或 alive 标记在弹出时识别并跳过。
详见 35-优先队列与堆。
31.6 十字链表与稀疏矩阵¶
S3 day2 讲 DLX 时用到了十字链表：
每个节点同时处在横排和竖排两个循环双向链表中。 最上面一排 \(C_1 \dots C_m\) 是辅助列头节点。
也就是每个节点有四个指针 L, R, U, D。Python 里同样用四个数组模拟：
# 四个方向的「指针数组」，存的都是节点编号：L/R 沿行走，U/D 沿列走
L = []; R = []; U = []; D = [] # 同一个节点同时挂在一横一竖两条循环链表上
col = [] # 该节点属于哪一列
row = [] # 该节点属于哪一行
用途：
- 稀疏矩阵：只存非零元，避免 \(n \times m\) 的空间；
- 精确覆盖 / DLX：数独、拼图密铺、N 皇后的统一框架。
Python 现实性：DLX 的核心是「删除—递归—撤销」的高频指针操作， 纯 Python 实现比 C++ 慢 30 倍以上。标准数独（\(9\times9\)）可行， 更大规模基本不可能。原理讲解见 115-高级搜索与精确覆盖。
31.7 例题¶
BISHI1 【模板】序列操作 —— 为什么它不该用链表¶
题面见 BISHI1 原题（牛客）， 详细讲解见 30-序列与数组。
这题的操作集合是链表的完美反例：
| 操作 | 数组 | 链表 |
|---|---|---|
3 i 按下标查 |
\(O(1)\) | \(O(i)\) |
4 i x 在下标 \(i\) 后插入 |
\(O(n)\)（memmove，C 层） | \(O(i)\) 找位置 + \(O(1)\) 插入 |
5/6 整体排序 |
\(O(n\log n)\)（Timsort） | 链表排序要归并，Python 层循环 |
8 输出全部 |
" ".join C 层 |
Python 层遍历 |
链表在每一项上都不占优：它省下的 \(O(n)\) 搬移是 C 层 memmove，
而它引入的 \(O(i)\) 定位是 Python 层循环。慢的那一半反而变多了。
判据：在 Python 里，「\(O(n)\) 的 C 层操作」通常比「\(O(n)\) 的 Python 层操作」快 50–100 倍。 所以只有当链表能把Python 层的 \(O(n)\) 降成 \(O(1)\) 时，它才值得写。
题解见 solutions/BISHI1.py。
BISHI96 先序遍历、中序遍历和后序遍历（简单）¶
给定 \(n \le 10^5\) 个节点的二叉树，以 \(n-1\) 条有向边 \((a_i, b_i)\) 给出（\(a_i\) 是父、\(b_i\) 是子）。 左右孩子规则：若有两个孩子，编号小的是左孩子；若只有一个孩子， 该孩子编号大于父节点编号时视为左孩子，否则视为右孩子。 输出先序、中序、后序遍历。 题面见 BISHI96 原题（牛客）。
二叉树本质上是「每个节点有两个 nxt 指针」的链表，所以放在本章。三个关键点：
1. 找根。 有向边 \(a \to b\) 意味着 \(b\) 有父亲。没有出现在任何 \(b\) 位置的点就是根。
2. 定左右孩子。 按题目规则：
if len(ch) == 2: # 两个孩子：题目规定编号小的挂左边
lc, rc = min(ch), max(ch)
elif len(ch) == 1: # 只有一个孩子，左右由它与父亲 u 的编号大小决定
c = ch[0]
if c > u: # 唯一孩子且编号更大 -> 左孩子
lc, rc = c, 0 # 0 不是合法节点编号，用来表示「这一侧为空」
else:
lc, rc = 0, c # 编号不大于父亲，按题目规则挂右边
3. \(n = 10^5\)，必须写迭代遍历。
Python 默认递归深度 1000，链状树的深度可达 \(10^5\)。
即使 sys.setrecursionlimit(300000)，CPython 的 C 栈也会先崩（Segmentation fault），
因为每层 Python 帧要占约 1KB 的 C 栈。
这是 Python 竞赛最经典的坑之一：
RecursionError你还能看到报错， C 栈溢出直接是运行时崩溃，没有任何提示。 解决方案有两个：改写成迭代（首选），或开大栈的子线程（下节）。
完整实现（迭代版三序遍历 + 建树）：
import sys
def preorder(root, lc, rc):
"""先序：根 -> 左 -> 右。用显式栈，右孩子先入栈。"""
res = []
st = [root] # 显式栈代替递归，n 可达 1e5，递归会压爆 C 栈
while st:
u = st.pop() # 栈顶就是下一棵待展开的子树根
res.append(u) # 先序：一出栈就访问，不用等孩子
if rc[u]: # 0 表示空孩子，非 0 才入栈
st.append(rc[u]) # 右孩子先压
if lc[u]:
st.append(lc[u]) # 左孩子后压先弹，顺序才是「根左右」
return res
def inorder(root, lc, rc):
"""中序：左 -> 根 -> 右。一路向左压栈，弹出后转右。"""
res = []
st = [] # 栈里是已压入但尚未访问的祖先
u = root # u 是下一棵待下潜的子树根，为 0 表示没有
while st or u: # 栈空且无待下潜节点才结束，两个条件缺一不可
while u: # 一路向左走到底，路过的节点全部压栈
st.append(u)
u = lc[u] # lc 为 0 时停下，此时栈顶是最左的节点
u = st.pop() # 弹出的节点左子树已走完
res.append(u) # 中序：左子树完毕后才访问根
u = rc[u] # 转向右子树；为 0 时下一轮直接继续弹栈
return res
def postorder(root, lc, rc):
"""后序：左 -> 右 -> 根。
技巧：先按「根 -> 右 -> 左」遍历，最后整体反转，
这样只需要一个栈，不用 visited 标记。
"""
res = []
st = [root] # 与先序同一副骨架，区别只在下面的入栈顺序
while st:
u = st.pop()
res.append(u)
if lc[u]: # 左孩子先压
st.append(lc[u])
if rc[u]:
st.append(rc[u]) # 右孩子后压先弹，于是遍历序是「根右左」
res.reverse() # 「根右左」整体反转就是「左右根」，即后序
return res
def main():
# 点数与 n-1 条边全在一个流里，整读成 token 后按游标推进最省事
data = sys.stdin.buffer.read().split()
n = int(data[0]) # 节点数
lc = [0] * (n + 1) # 左孩子表；开 n+1 让下标直接当编号，0 表示空
rc = [0] * (n + 1) # 右孩子表，含义同上
has_parent = bytearray(n + 1) # 每格 1 字节的标记数组，比布尔列表省 8 倍内存
# 先按输入顺序收下每个点的孩子，之后再定左右；写成 [[]] * (n + 1) 会让各行共用同一个列表
ch = [[] for _ in range(n + 1)]
p = 1 # token 游标，data[0] 已被 n 取走
for _ in range(n - 1): # n 个点的树恰有 n-1 条边
a = int(data[p]); b = int(data[p + 1]); p += 2 # 每条边两个 token，游标推进 2
ch[a].append(b) # 边是有向的：a 是父，b 是子
has_parent[b] = 1 # b 出现在子端，说明它有父亲
root = 1 # 兜底：n = 1 时没有边，1 号自己就是根
for i in range(1, n + 1):
if not has_parent[i]: # 没有父亲的点就是根，二叉树里它唯一
root = i
break # 根唯一，找到即可停
for u in range(1, n + 1): # 逐点把孩子列表翻译成 lc/rc
c = ch[u]
if len(c) == 2: # 两个孩子：小的是左，大的是右
lc[u], rc[u] = min(c), max(c)
elif len(c) == 1: # 一个孩子：编号大于父亲则为左孩子
if c[0] > u: # 未被赋值的那一侧保持 0，即空孩子
lc[u] = c[0]
else:
rc[u] = c[0]
out = [] # 三行输出先攒着
for f in (preorder, inorder, postorder): # 先序、中序、后序各输出一行
out.append(" ".join(map(str, f(root, lc, rc))))
sys.stdout.write("\n".join(out) + "\n") # 一次写出，逐行 print 的 IO 开销显著
main()
复杂度 \(O(n)\)，三次遍历共约 \(3 \times 10^5\) 次 Python 层循环，稳过。
验证样例（n=2，边 1 2）：节点 1 只有一个孩子 2，且 \(2 > 1\) \(\Rightarrow\) 左孩子。
先序 1 2、中序 2 1、后序 2 1 ✓
附：递归深度的两种应急方案¶
# [片段]
# 方案 1（首选）：改写成迭代 —— 上面就是
# 方案 2：开大栈的子线程运行（当递归实在难改写时）
import sys
import threading
def main():
...
sys.setrecursionlimit(1 << 20) # 1 << 20 约 100 万层，先抬高 Python 的计数上限
threading.stack_size(1 << 26) # 1 << 26 = 64MB 线程栈；真正卡住递归的是 C 栈
t = threading.Thread(target=main) # 主线程的栈大小改不了，只能另起线程
t.start()
t.join() # 等它跑完再退出，否则主线程先结束会丢输出
sys.setrecursionlimit只改 Python 的计数器，不改 C 栈大小。 单独调它而不换线程，结果是把RecursionError换成了段错误——更糟。 两者必须配套使用。详见 20-输入输出处理 与 60-DFS深度优先搜索。
题解：solutions/BISHI96.py（已通过牛客判题机验证）
31.8 本章速查¶
| 要点 | 结论 |
|---|---|
| Python 里写链表 | 用数组模拟（nxt/pre 整型数组），不要 class Node |
class Node 的代价 |
比数组模拟慢 5–10 倍，内存数倍 |
| 链表的唯一优势 | 已知节点时 \(O(1)\) 删除/插入 |
| 链表的死穴 | 按下标访问是 \(O(k)\) |
| 何时该用链表 | 只删不加 + 删除时已知目标 + 需要左右邻居 |
| 何时不该用 | 需要下标访问、需要排序、需要求和 |
| 「依次删除」类问题 | 倒序处理变成加点 → 并查集（38 章） |
| 删除的撤销 | 保留被删节点的 pre/nxt 即可 \(O(1)\) 还原（DLX 核心） |
| 约瑟夫问题 | 小数据链表模拟 \(O(nm)\)；只要幸存者用递推 \(O(n)\) |
| 二叉树 \(n = 10^5\) | 必须迭代遍历，递归会爆 C 栈 |
setrecursionlimit |
只改计数器，必须配 threading.stack_size |
| 遍历 | 迭代实现要点 |
|---|---|
| 先序 | 单栈，右孩子先入栈 |
| 中序 | 一路向左压栈，弹出后转右 |
| 后序 | 按「根右左」遍历后 reverse() |