🏠 总目录📚 本教程 01 · 链表:指针到底在保住什么 ← →
📑 本页目录(点开跳转)

01 · 链表:指针到底在保住什么

⏱ 12 分钟 | 反转、合并、环入口:全是“先别把下一站弄丢”

🎯 一句话

链表题的核心不是指针语法,而是:改 next 之前,先把旧的下一站存下来。

先辨认节点,再动箭头

两张待办卡都写着 7。要移走第二张,只看数字会挑错。我们给三张卡标上 A、B、C 来辨认它们,标记只用于画图。

单向链表(singly linked list)像一串只能顺着走的卡片。每张卡是一个节点(node),val 是它的值,next 保存下一张卡的引用(reference)。head 保存第一张卡的引用,None 表示无节点。A 和 B 的 val 都是 7,它们仍是两个节点。

从头能走到哪里?A(7)→ B(7)→ C(9)→ None。A 是 B 的前驱,也就是 B 前一个节点。
先读 B 的后路A.next 找到 B,B.next 找到 C。需要接回的是 C。
让 A 跳过 B执行 A.next = B.next。现在沿 head 只走过 A(7)→ C(9)→ None。

已持有前驱 A 时,这次删除只读写固定数量的链接,记作 O(1)。如果只持有 B,一般得从 head 顺着箭头找它的前驱。最坏要检查的节点数随链长 n 增长,记作 O(n)。这两个记号描述操作量如何随输入增长,第 04 章会用排序例子比较几种增长方式。

头节点没有前驱。要移走头节点且链表非空,就把入口 head 改成旧头的 next。若别的变量仍引用被跳过的节点,它依然可以从那个变量访问。

🧩 题 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 为止 1 2 dummy.next tail 两条待处理链表 a 3 5 b 4 虚线是 2 原来的 next;下一轮比较 3 和 4,再把 2 接到 3。
看清两件事:实线前缀 1、2 已经有序;虚线旧链接不表示 4 已被选入结果。
时刻 已确认的前缀(截至 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 走两步;是在移动之后比较是否为同一个节点,不把起点重合作为发现环。

按本页四个节点走一遍

1234 头节点入口:节点 24 的 next 回到 2
看底部回绕的箭头:环是 2、3、4,头节点 1 在环外。
检查时刻 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。


⚡ 走神救援

继续: 02 · 树:递归到底在替你保存什么

打卡记录保存在你的浏览器里,首页能看到总进度