📑 本页目录(点开跳转)
01 · 链表:指针到底在保住什么
⏱ 12 分钟 | 反转、合并、环入口:全是“先别把下一站弄丢”
🎯 一句话
链表题的核心不是指针语法,而是:改 next 之前,先把旧的下一站存下来。
先辨认节点,再动箭头
两张待办卡都写着 7。要移走第二张,只看数字会挑错。我们给三张卡标上 A、B、C 来辨认它们,标记只用于画图。
单向链表(singly linked list)像一串只能顺着走的卡片。每张卡是一个节点(node),val 是它的值,next 保存下一张卡的引用(reference)。head 保存第一张卡的引用,None 表示无节点。A 和 B 的 val 都是 7,它们仍是两个节点。
A.next 找到 B,B.next 找到 C。需要接回的是 C。A.next = B.next。现在沿 head 只走过 A(7)→ C(9)→ None。已持有前驱 A 时,这次删除只读写固定数量的链接,记作 O(1)。如果只持有 B,一般得从 head 顺着箭头找它的前驱。最坏要检查的节点数随链长 n 增长,记作 O(n)。这两个记号描述操作量如何随输入增长,第 04 章会用排序例子比较几种增长方式。
头节点没有前驱。要移走头节点且链表非空,就把入口 head 改成旧头的 next。若别的变量仍引用被跳过的节点,它依然可以从那个变量访问。
🔎 可选深入:链表改接快,为什么查找仍可能慢?
改 next 之前先保住后路,是因为链式节点把“下一项在哪”存在链接里。数组模型则把元素按位置排开。先说清是否已经定位到插删位置,再比较复杂度。
| 操作/成本 | 连续数组模型 | 本页单向链式节点 |
|---|---|---|
| 随机访问第 i 项 | 按下标定位通常 O(1) | 从头沿 next 找到它通常 O(n) |
| 已知位置插入/删除 | 中间操作需搬移后续项,通常 O(n) | 已持有前驱及必要链接时,改接为 O(1);寻找前驱仍可能 O(n) |
| 存储与遍历 | 通常局部性较好;扩容/搬移有额外成本 | 每节点有链接与分配开销;节点可能分散,局部性依实际分配 |
例如在 1 → 3 → 5 中,把新节点 2 插在已持有的节点 1 后面,只需 new.next = node1.next,再 node1.next = new。若题目只给“在值为 3 的节点前插入”,还要先查找并保住前驱;不能把整道操作都称为 O(1)。
本页代码使用 Python 节点对象,这不是在复刻 C++ 的内存布局。Python list 是序列接口,不能拿这里的概念表断言它与 C++ vector 的对象存储、扩容或迭代器失效完全相同。实际选型还要看访问模式和分配成本。
实现/接口边界可对照 C++ vector 与 forward_list;本表比较通用数组/单链模型,不展开 STL 实现。
🧩 题 1:反转链表
题目。 1 → 2 → 3 变成 3 → 2 → 1。
先画。 prev 是已经翻好的部分;cur 是还没处理的第一个节点;nxt 临时保住后路。
不变量。 每轮结束后,prev 指向已反转的前缀,cur 指向尚未处理的后缀。这里“指向”就是变量保存着对应节点对象;next 保存下一节点,None 表示没有下一站。
先跟第一轮,不急着看完整循环
开始时 prev 是 None,cur 是节点 1。下面每行只做一件事:
| 执行到哪一行 | prev | cur | nxt | 刚发生了什么 |
|---|---|---|---|---|
| 开始 | None | 1 | 尚未设置 | 原链仍是 1 → 2 → 3 |
| nxt = cur.next | None | 1 | 2 | 保住原来的下一站 2 |
| cur.next = prev | None | 1 | 2 | 1 的 next 改成 None;2、3 仍可从 nxt 找到 |
| prev, cur = cur, nxt | 1 | 2 | 2 | 已翻部分的头是 1,下一轮处理 2 |
关键在第二次赋值: 如果没先保存 nxt,就会用 None 覆盖唯一能从当前节点继续找到 2 的链接。
| 完成轮数 | 已反转部分(prev 开头) | 尚未处理部分(cur 开头) |
|---|---|---|
| 1 | 1 | 2 → 3 |
| 2 | 2 → 1 | 3 |
| 3 | 3 → 2 → 1 | 空,cur 为 None |
现在再看代码:循环结束返回的是 prev,不是已经走到 None 的 cur。程序的 assert 不打印内容;正常执行结束且没有 AssertionError,就是本例断言通过。
class ListNode:
def __init__(self, val, next=None):
self.val, self.next = val, next
def reverse_list(head):
prev, cur = None, head
while cur:
nxt = cur.next # 先保住后路
cur.next = prev # 再掉头
prev, cur = cur, nxt # 两队伍一起向前
return prev
def values(head):
out = []
while head:
out.append(head.val)
head = head.next
return out
head = ListNode(1, ListNode(2, ListNode(3)))
assert values(reverse_list(head)) == [3, 2, 1]
⚠️ 最常见的错:先写 cur.next = prev,再想找原来的 cur.next。这时后路已经被覆盖,沿 cur 就找不到原来的后缀了。
输入边界。反转接收无环链表。空链不进循环,返回 None。单节点只翻一次,prev 就是这个节点。输入若是有环结构,普通的反转不再保证得到本题定义的结果。
数循环。一轮只处理一个原节点。示例的 3 个节点执行 3 轮,n 个节点执行 n 轮,时间 O(n)。原节点直接改接,只增加固定数量的引用,额外空间 O(1)。演示中的 values() 会收集列表,它的空间不计入反转函数。
🧩 题 2:合并两个有序链表
题目。 把 1 → 3 → 5 和 2 → 4 合成 1 → 2 → 3 → 4 → 5。
不变量。 循环中,已经选好的结果是从 dummy.next 到 tail 的这一段;tail 是这段的末尾。a、b 各指向一条待处理链表的第一个节点。
不要把 tail.next 当成“已经合并好的后半段”。 原节点的旧链接可能还在,下一轮才会改接它。
看一次中途状态:刚选完 1 和 2
| 时刻 | 已确认的前缀(截至 tail) | a 指向 | b 指向 |
|---|---|---|---|
| 刚开始 | 空;tail 还是 dummy | 1 | 2 |
| 选完 1 | 1 | 3 | 2 |
| 选完 2 | 1、2 | 3 | 4 |
| 循环结束 | 1、2、3、4 | 5 | None |
最后的 tail.next = a or b 把剩余有序链表一次接上。本例接上 5 后,tail 变量仍指向 4,但返回的完整结果已经是 1、2、3、4、5。
class ListNode:
def __init__(self, val, next=None):
self.val, self.next = val, next
def merge_sorted(a, b):
dummy = ListNode(0)
tail = dummy
while a and b:
if a.val <= b.val:
tail.next, a = a, a.next
else:
tail.next, b = b, b.next
tail = tail.next
tail.next = a or b
return dummy.next
def values(head):
out = []
while head:
out.append(head.val)
head = head.next
return out
a = ListNode(1, ListNode(3, ListNode(5)))
b = ListNode(2, ListNode(4))
assert values(merge_sorted(a, b)) == [1, 2, 3, 4, 5]
💡 dummy 只是一个假头:这样第一个节点也和后面的节点一样接,不必写“第一次特殊处理”。
输入边界。两条输入各自无环、按值非递减,且没有共享节点。若两条链共享尾部,改接时可能把同一个节点接到自己身上。某条输入为空时不做比较,直接接另一条。两边值相等时,这份代码先取 a 的节点,再让它继续向前,同值节点都会保留。
数比较。设两条链分别有 m、n 个节点。每次比较确定一个结果节点,一条链用完就接余下整段。上例 m = 3、n = 2,先后比较了 1 和 2、3 和 2、3 和 4、5 和 4,共四次,最后直接接 5。两条都非空时比较次数至多 m + n − 1,最坏时间 O(m + n)。复用输入节点,只额外创建一个假头并保留固定数量的引用,额外空间 O(1)。
🧩 题 3:链表中环的入口
题目。 链表可能绕回去。返回绕回的第一个节点;没有环则返回 None。
先分清“发现环”和“找到入口”。 slow 每轮走一步,fast 走两步;是在移动之后比较是否为同一个节点,不把起点重合作为发现环。
按本页四个节点走一遍
| 检查时刻 | slow(每轮一步) | fast(每轮两步) | 是否相遇 |
|---|---|---|---|
| 移动前 | 1 | 1 | 起点不算,先移动 |
| 第一轮后 | 2 | 3 | 否 |
| 第二轮后 | 3 | 2 | 否 |
| 第三轮后 | 4 | 4 | 是,但 4 不是入口 |
相遇后,新增 seeker 指向头节点 1,slow 留在 4。两者现在都每轮走一步:seeker 到 2,slow 也到 2,因此找到入口。
为什么从头同速走,能找到入口?
记头到入口的步数为 a,环长为 L,第一次相遇时 slow 走了 t 步。
fast 走了 2t 步,比 slow 多走 t 步。两者在环中同一节点相遇,说明 t 是环长 L 的整数倍。
slow 此时相对入口的位置是 (t − a) 对 L 取余。再走 a 步,总偏移变成 t,正好绕回入口;从头出发的 seeker 走 a 步也到入口。seeker 到入口前在环外,不会提前与环里的 slow 相遇。
本例 a = 1,L = 3,t = 3。相遇点离入口的环内偏移是 (3 − 1) 除以 3 余 2。再走 1 步,偏移为 2 + 1 = 3,除以 3 余 0,回到入口。这个证明依赖“先一倍速与二倍速发现环,再同速定位”的设置,不能任意更换速度后照搬。
如果没有环,fast 会到 None,或它的 next 是 None;代码就返回 None。比较用 is,判断同一节点对象,而不是两个节点的 val 是否相同。
class ListNode:
def __init__(self, val, next=None):
self.val, self.next = val, next
def cycle_entry(head):
slow = fast = head
while fast and fast.next:
slow, fast = slow.next, fast.next.next
if slow is fast:
break
else:
return None
seeker = head
while seeker is not slow:
seeker, slow = seeker.next, slow.next
return seeker
n1, n2, n3, n4 = ListNode(1), ListNode(2), ListNode(3), ListNode(4)
n1.next, n2.next, n3.next, n4.next = n2, n3, n4, n2
assert cycle_entry(n1) is n2
距离解释可以按需展开。先记住使用条件:一个快、一个慢能确认“是否绕圈”;确认后,同速从头和相遇点出发能找到入口。
输入边界。空链和单个不自连的节点都返回 None。单个节点指向自己时,两人移动一次后就在头节点相遇。此时 seeker 与 slow 一开始就相同,第二阶段走零步,入口就是头节点。
为什么不会一直追不上?一旦两人都在环上,快指针每轮相对慢指针多走一步。设环长 L 是绕一圈要跨过的箭头数,最多再走 L 轮就会同处一个节点。设从头能到达的不同节点数为 n。无环时快指针会触及空链接。有环时,头到入口的步数和环长加起来就是 n,定位阶段最多再走头到入口的那段距离。因此最坏时间 O(n),额外空间 O(1),全程只移动引用而无需改写链表。
🔗 这一章连到哪里
| 去哪 | 为什么 |
|---|---|
| Python 会咬你的地方 01 · 名字、对象和绑定 | ⭐ 「先保住后路再掉头」为什么必须这么写:Python 里赋值从不复制对象,只是把名字重新贴一次。prev, cur = cur, nxt 这种多重赋值的求值顺序也在那一章 |
本节回顾
链表所有“改指针”的题,先问:我改掉这条线之前,下一站放哪了?
✅ 检查点
反转链表时为什么一定先保存 nxt?
👀 看答案
因为下一步会覆盖 cur.next。不先保存,原来尚未处理的后缀就再也找不到了。
卡片 A(7)→ B(7)→ C(9)。你手里有 A 和 B,怎样移走 B?如果只拿着 B,而且它不是头节点,还缺什么?
👀 看改接步骤
读 B 的下一站 C,把 A.next 改成 C。若只拿着 B,还缺指向 B 的那条箭头的起点 A。单链只能向前,一般要从头找这个前驱。
合并 1 → 4 与 2 → 3,两条链不共享节点。选完 1 和 2 后,下一次选谁?剩下的节点还要比较吗?
👀 看合并步骤
比较 4 和 3,选 3。此时右链已空,把尾巴接到左链剩下的 4 即可。总共做了 3 次比较,输出顺序是 1、2、3、4。
若 A → B → C → None 中 B 和 C 的值都为 7,第一轮只比较值会怎样?比较节点身份呢?
👀 看快慢指针走法
第一轮 slow 到 B、fast 到 C。仅比较值会误报相遇,用 is 则知道它们是两个节点。随后快指针不能再走两步,算法返回 None。
⚡ 走神救援
- 反转:
nxt保后路,prev是已翻好的头。 - 合并:从
dummy.next到tail是已确认的有序前缀;a、b是待处理入口。 - 环入口:快慢先相遇;一个回头后,两人同速再见就是入口。