第 31 章 链表¶
链表在 C/C++ 里是必修课，在 Python 里却是最容易被误用的数据结构——
因为 Python 没有指针，手写 Node 类的常数大到几乎不可能通过任何 \(10^5\) 级别的题。
这一章的目标不是教怎么写 class Node，而是回答两个问题：
什么时候真的需要链表？以及在 Python 里应该用什么形式实现它？
1 链表的四种形态¶
| 形态 | 每个节点存 | 支持的操作 |
|---|---|---|
| 单向链表 | data、nxt |
已知前驱时 \(O(1)\) 插入/删除，只能单向走 |
| 双向链表 | data、pre、nxt |
已知节点本身即可 \(O(1)\) 删除，双向走 |
| 循环链表 | 首尾相接 | 从任意元素出发可遍历全部（约瑟夫问题） |
| 十字链表 | 同时属于横、竖两条双向循环链表 | 稀疏矩阵、Dancing Links |
教科书的单链表是标准的带头结点写法：h 是哑结点（哨兵），
真正的第一个元素是 h->next。带头结点的好处是插入删除不需要特判空表。
链表和数组的本质取舍只有一句话：
数组（list） |
链表 | |
|---|---|---|
| 按下标访问第 \(k\) 个 | \(O(1)\) | \(O(k)\) |
| 已知位置后插入/删除 | \(O(n)\)（要搬移） | \(O(1)\) |
| 内存 | 连续，缓存友好 | 分散，每节点多存 1–2 个指针 |
一句话点破：「如果没有辅助数组，链表无法快速访问内部元素。」 这正是链表的死穴——必须先有一个指向目标节点的引用， 而拿到这个引用本身往往就要 \(O(n)\)。
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只在面试白板题、以及题目本身就给定链表结构时用。 纯算法题一律不要用。
写法 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)\) 删除吗？ 如果不需要，别写链表。
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 为什么能工作¶
Dancing Links 点破了这个技巧：
回忆循环链表的删除操作。如果保留
x->pre和x->nxt的值不变， 那么可以通过x->pre->nxt = x; x->nxt->pre = x;把x还原到链表中。
也就是说，被删除的节点自己还记得原来站在哪两个人中间。 这让「删除—递归—撤销」变成 \(O(1)\)，是 DLX 求解精确覆盖的基础， 详见 精确覆盖与 Dancing Links。
4 经典应用一：约瑟夫问题¶
\(n\) 个人围成一圈，从第 1 个人开始报数 \(1, 2, 3, \dots\)， 数到 \(m\) 的人出列，然后从下一个人重新从 1 开始报。依次输出出列的编号。
解法 1：循环链表模拟，\(O(nm)\)¶
数据范围小（原题是 \(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\) 个存活者。见 树状数组。
5 经典应用二：需要「\(O(1)\) 任意删除」的题¶
这才是链表在竞赛中真正不可替代的场景。识别特征：
元素只删不加，且删除时已经知道要删谁（不需要查找）。
典型题型：
| 题型 | 做法 |
|---|---|
| 按某种顺序依次删除元素，每次要知道左右邻居 | 数组模拟双向链表 |
| 「删除后合并相邻元素」的贪心 | 链表 + 堆（堆里存邻居对，懒删除） |
| 倒序处理「删点」问题 | 反过来变成「加点」，用并查集 |
最后一条特别重要：
删除不好处理，倒过来变成添加，就变成并查集的拿手好戏了。
所以看到「依次删除若干元素，每次问连通性/集合大小」， 标准套路是离线倒序 + 并查集，而不是链表。见 并查集。
「链表 + 堆」的懒删除套路¶
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 标记在弹出时识别并跳过。
详见 优先队列与堆。
6 十字链表与稀疏矩阵¶
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\)）可行， 更大规模基本不可能。原理讲解见 精确覆盖与 Dancing Links。
7 例题¶
| 题号 | 题名 | 难度 | 题解 |
|---|---|---|---|
| BISHI1 | 【模板】序列操作 | 简单 | 题解 |
| BISHI96 | 先序遍历、中序遍历和后序遍历 | 简单 | 题解 |
| BM1 | 反转链表 | 简单 | 题解 |
| BM2 | 链表内指定区间反转 | 中等 | 题解 |
| BM3 | 链表中的节点每k个一组翻转 | 中等 | 题解 |
| BM4 | 合并两个排序的链表 | 简单 | 题解 |
| BM6 | 判断链表中是否有环 | 简单 | 题解 |
| BM7 | 链表中环的入口结点 | 中等 | 题解 |
| BM8 | 链表中倒数最后k个结点 | 简单 | 题解 |
| BM9 | 删除链表的倒数第n个节点 | 中等 | 题解 |
| BM10 | 两个链表的第一个公共结点 | 简单 | 题解 |
| BM11 | 链表相加(二) | 中等 | 题解 |
| BM13 | 判断一个链表是否为回文结构 | 简单 | 题解 |
| BM14 | 链表的奇偶重排 | 中等 | 题解 |
| BM15 | 删除有序链表中重复的元素-I | 简单 | 题解 |
| BM16 | 删除有序链表中重复的元素-II | 中等 | 题解 |
| BM100 | 设计LRU缓存结构 | 较难 | 题解 |
| LC206 | 反转链表 | 简单 | 题解 |
| LC2 | 两数相加 | 中等 | 题解 |
| LC19 | 删除链表的倒数第 N 个结点 | 中等 | 题解 |
| LC21 | 合并两个有序链表 | 简单 | 题解 |
| LC23 | 合并 K 个升序链表 | 困难 | 题解 |
| LC24 | 两两交换链表中的节点 | 中等 | 题解 |
| LC25 | K 个一组翻转链表 | 困难 | 题解 |
| LC138 | 随机链表的复制 | 中等 | 题解 |
| LC141 | 环形链表 | 简单 | 题解 |
| LC142 | 环形链表 II | 中等 | 题解 |
| LC146 | LRU 缓存 | 中等 | 题解 |
| LC148 | 排序链表 | 中等 | 题解 |
| LC160 | 相交链表 | 简单 | 题解 |
| LC234 | 回文链表 | 简单 | 题解 |
BISHI1 【模板】序列操作 —— 为什么它不该用链表¶
这题的操作集合是链表的完美反例：
| 操作 | 数组 | 链表 |
|---|---|---|
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/nowcoder/BISHI1/sol.py。
BISHI96 先序遍历、中序遍历和后序遍历（简单）¶
给定 \(n \le 10^5\) 个节点的二叉树，以 \(n-1\) 条有向边 \((a_i, b_i)\) 给出（\(a_i\) 是父、\(b_i\) 是子）。 左右孩子规则：若有两个孩子，编号小的是左孩子；若只有一个孩子， 该孩子编号大于父节点编号时视为左孩子，否则视为右孩子。 输出先序、中序、后序遍历。 题面见 原题。
二叉树本质上是「每个节点有两个 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换成了段错误——更糟。 两者必须配套使用。详见 输入输出处理 与 DFS深度优先搜索。
题解：solutions/nowcoder/BISHI96/sol.py（已通过判题机验证）
面试题单里的十六道链表题¶
这一批题与 §2 的结论并不矛盾：节点由题面构造好传进来，不是在解法里逐个新建的， 「\(10^5\) 次对象分配」的代价题目已经替解法付过了。剩下的活只有一件—— 在给定节点上正确地改指针。按套路分组之后，组内的题基本是同一份模板改三五行。
哑结点 ＋ 三指针原地反转。
反转链表（同一道题在另一处题库里编号 LC 206. 反转链表）是整条反转，
pre / cur / nxt 三个变量走一遍，额外空间 \(O(1)\)。
链表内指定区间反转把范围收窄到 \([m, n]\)，难点是 \(m = 1\) 时「反转段的前驱」不存在——
哑结点正是为这一个特判而生的，加上它之后 \(m = 1\) 与 \(m > 1\) 共用同一条代码路径。
链表中的节点每k个一组翻转再进一步：每组动手前先向前数够 k 个节点，
数不满就整组保持原序返回；漏掉这一步，尾部不足 k 个的残段会被一起翻掉。
快慢指针：把「倒数第 k 个」与「有没有环」都压成一次遍历。 链表中倒数最后k个结点让快指针先走 k 步，两指针再同步前进， 快指针到尾时慢指针恰好停在答案上。删除链表的倒数第n个节点是同一招加一个哑结点—— 被删的可能正是头节点。判断链表中是否有环把两指针的步长改成 1 和 2，相遇即有环； 链表中环的入口结点接着做第二阶段：相遇后把一个指针放回表头、两边同步单步走， 再次相遇处就是入口。这两题用哈希表存「见过的节点」同样能过， 但要多占 \(O(n)\) 空间，而快慢指针是 \(O(1)\)。 两个链表的第一个公共结点用的是同一类位移技巧：两个指针分别从两条表头出发， 走到尽头就跳到对方表头，各自走过 \(len_a + len_b\) 步后必在公共点相遇； 没有公共点时两者同时变空而退出，不会死循环。
先拆再接。 链表的奇偶重排把奇数位与偶数位拆成两条链再首尾相接，
拆的时候两条链各留一个尾指针，省掉每次从头找尾的 \(O(n)\)。
判断一个链表是否为回文结构先用快慢指针定位中点，反转后半段再逐位比对，
额外空间 \(O(1)\)；若允许 \(O(n)\) 空间，把值倒进 list 后 a == a[::-1] 是 C 层比较，
代码短、常数也更小——这正是 §2 反复说的那条取舍。
有序表上的删重，两题差一个字。 删除有序链表中重复的元素-I保留每段的第一个，
一个游标就够；删除有序链表中重复的元素-II一个不留，
既要哑结点（头部整段可能被删光），又要「先探后删」：
确认 cur.next.val == cur.next.next.val 之后才整段跳过。题面差一个字，代码结构差一层。
归并与进位。 合并两个排序的链表就是归并排序的合并步单独拎出来：
哑结点接尾、谁小接谁、循环结束后把剩下那条整条挂上。
链表相加(二)的数位是高位在前，而加法要从低位起，两条路都通——
整条反转后相加再反转回来，或者两条链分别压栈后逐层弹出；后者不改动原链，代价是 \(O(n)\) 栈空间。
进位变量要在循环外再判一次，否则 9 + 1 会丢掉最高位。
设计LRU缓存结构：这一章唯一「非链表不可」的题。
get 与 set 都要求 \(O(1)\)，而 LRU 需要「把某个已知节点挪到表头」和「删掉表尾」两种操作，
正是 §1 那张表里链表唯一占优的那一格。标准结构是哈希表存「键 → 节点」、
双向链表按访问时间排序，两者缺一不可：只有哈希表则定位不到前驱，只有链表则查找退化成 \(O(n)\)。
Python 里还有一条捷径：collections.OrderedDict 的 move_to_end 与 popitem(last=False)
就是 C 层实现的同一套结构，把双向链表的维护整个挪到了 C 层。
另一处题库里的十三道链表题¶
这十三道题与上一节的十六道有大面积重叠：九道是同一套模板换个题面， 真正带来新套路的只有四道。分开列，是为了把「换了什么」这件事本身说清楚。
九道同模板的，只记差异。 LC 25. K 个一组翻转链表与 BM3 是同一题，边界要求一字不差：不足 k 个的残段保持原序。 LC 21. 合并两个有序链表对应 BM4，哑结点接尾、谁小接谁。 LC 19. 删除链表的倒数第 N 个结点对应 BM9，快指针先走 N 步，再加一个哑结点兜住「删的正是头节点」。 LC 141. 环形链表与 LC 142. 环形链表 II 正是 BM6 与 BM7 的两个阶段： 前者只问有没有环，后者还要给出入口。 LC 160. 相交链表对应 BM10，两个指针走完各自的表就跳到对方表头。 LC 234. 回文链表对应 BM13，快慢指针定位中点、反转后半段、逐位比对。 LC 2. 两数相加与 BM11 链表相加(二) 差一个方向：LC2 的数位低位在前，反而更省事—— 同步遍历累加进位即可，不必先反转；BM11 高位在前才要多做两次反转或整条压栈。 LC 146. LRU 缓存与 BM100 是同一个结构：哈希表定位 ＋ 双向链表按访问时间排序。
LC 24. 两两交换链表中的节点：三指针模板的定长特例。
它等价于把 LC25 的 k 固定成 2，于是「先向前数够 k 个」那一步可以省掉，
每轮只判 pre.next 与 pre.next.next 是否都存在。
写成递归只有三行，但递归深度等于节点数，\(10^5\) 长的链会直接触发栈溢出；
迭代版额外空间 \(O(1)\)，是能过大数据的那一版。
LC 23. 合并 K 个升序链表：合并步从两条推广到 K 条。
逐条往结果链上合是 \(O(K^2 n)\)——第 \(i\) 次合并要重扫已经合好的 \(i \cdot n\) 个节点。
两条路把它压到 \(O(Kn \log K)\)：分治两两归并（每层总代价 \(O(Kn)\)，共 \(\lceil \log_2 K \rceil\) 层），
或者堆里始终只放 K 个链头，每弹出一个就把它的后继压回去。
后者与本章「链表 ＋ 堆」的懒删除套路是同一个结构，区别只在这里不需要删除标记。
heapq 比较的是元组，而节点对象本身不可比较，所以要压 (val, idx, node) 三元组，
中间那个序号是为了 val 相等时不至于去比较节点。
LC 148. 排序链表：唯一要求 \(O(1)\) 额外空间的排序题。 把值倒进列表排完再写回是 \(O(n)\) 空间、\(O(n \log n)\) 时间，且排序在 C 层完成， \(10^5\) 个节点上是耗时最短的一版。要满足 \(O(1)\) 空间就只剩自底向上的归并： 步长从 1 开始逐轮翻倍，每轮把相邻两段拆下来合并再接回，共 \(\lceil \log_2 n \rceil\) 轮。 快速排序在链表上不可行的原因是它要从两端向中间走，而单链表只能单向前进。
LC 138. 随机链表的复制：多出一条不指向后继的边。
random 指针可能指向任意节点甚至为空，复制时目标节点往往还没被创建出来。
哈希表版扫两遍：第一遍只建节点并记下「原节点 → 新节点」，第二遍再接 next 与 random，
额外空间 \(O(n)\)。\(O(1)\) 额外空间的版本扫三遍：先把每个新节点插在原节点后面交织成一条链，
此时 cur.random.next 恰好就是新节点该指向的目标；接完 random 再把两条链拆开。
交织法省下的是哈希表，代价是三遍遍历与一次拆链。
8 本章速查¶
| 要点 | 结论 |
|---|---|
| Python 里写链表 | 用数组模拟（nxt/pre 整型数组），不要 class Node |
class Node 的代价 |
比数组模拟慢 5–10 倍，内存数倍 |
| 链表的唯一优势 | 已知节点时 \(O(1)\) 删除/插入 |
| 链表的死穴 | 按下标访问是 \(O(k)\) |
| 何时该用链表 | 只删不加 + 删除时已知目标 + 需要左右邻居 |
| 何时不该用 | 需要下标访问、需要排序、需要求和 |
| 「依次删除」类问题 | 倒序处理变成加点 → 并查集（并查集） |
| 删除的撤销 | 保留被删节点的 pre/nxt 即可 \(O(1)\) 还原（DLX 核心） |
| 约瑟夫问题 | 小数据链表模拟 \(O(nm)\)；只要幸存者用递推 \(O(n)\) |
| 二叉树 \(n = 10^5\) | 必须迭代遍历，递归会爆 C 栈 |
setrecursionlimit |
只改计数器，必须配 threading.stack_size |
| 遍历 | 迭代实现要点 |
|---|---|
| 先序 | 单栈，右孩子先入栈 |
| 中序 | 一路向左压栈，弹出后转右 |
| 后序 | 按「根右左」遍历后 reverse() |