单向链式结构不一定以 null 结尾:一个错误的链接可能指回先前的某个节点,此时打印循环可能会永远运行下去。Floyd 的快慢指针方法只需常数大小的额外指针存储即可检测环,并能定位环的入口。该方法适用于有限且稳定的结构,其中每个节点只有一个 next 指针;它不要求节点的值互不相同。应比较节点身份,而不是节点中存储的值。
环检测是链表追踪的延伸应用。
定义 2.2.1
(尾长与环长)
从 head 沿 next 前进。若序列到达 null,结构为无环。否则某个节点被经过两次,入口就是首个被经过两次的节点。设 为由 head 到入口的链接数(尾长), 为由入口开始的环所含的节点数。从 head 可到达的 个节点全部互不相同。环问题的输入是 head:若可到达环,返回环上的一个节点,否则返回 null。
1. 在任何证明之前先做到安全检测
假设从 head 出发沿 next 前进,最终要么到达 null,要么重复访问某个节点。借助语言中短路求值的 and,算法如下:
slow = head
fast = head
while fast != null and fast.next != null:
slow = slow.next
fast = fast.next.next
if slow == fast: # compare node identities
return slow # a meeting node, not necessarily the entry
return null # no reachable cycle
(代码注释含义:# compare node identities 表示"比较节点身份";# a meeting node, not necessarily the entry 表示"相遇节点,不一定是入口";# no reachable cycle 表示"不存在可达的环"。)
循环条件必须先检查 fast,再访问 fast.next。更新操作是安全的:当 fast.next 存在时,即使 fast.next.next 为 null,它也是一个合法的指针值。在无环路径上,slow 落后于 fast,因此在该时刻非空;在有环路径上,两个指针都不会到达 null。若 head 为 null,循环不会执行。若单节点链表以 null 结尾,循环同样不会执行。而自环则会在第一次迭代时产生相遇。只在移动之后检查相等性,可以避免初始时的相等 slow == fast == head 在非空无环链表中被误报为环。
若链表到达 null,快指针至多经过其有限个节点,循环条件最终会不成立。在这样的路径上,没有节点能被访问两次,因此慢指针和快指针在走过正的且不相等的步数之后,不可能在某个非空节点相遇。若存在环,两个指针最终都会进入环中;下一节将说明为什么它们此后必然相遇。
常见错误
(比较存储的值而不是节点身份)
取五个节点的无环链表 null,各节点的值为 。第一次迭代后两个指针在 和 ,第二次迭代后在 和 。这两个节点的值都是 ,所以按值比较会在没有环的链表中报告有环。 与 的身份不同,身份比较就会正确地继续,随后由循环条件在 null 处停止。
常见错误
(在第一次移动之前就检查相遇)
若把相等检查放在指针移动之前,对每个非空链表,一开始 slow == fast(两者都等于 head)就成立,于是每个链表都会被报告为有环。对无环链表 null,正确的循环只迭代一次,此时 slow 在 、fast 为 null,并返回 null。因此最早可能的相遇时间是 ,也因此在 时首次相遇在 而不是 。
2. 用距离解释相遇点和入口
经过 次循环迭代后,慢指针走了 条链接,快指针走了 条。当 时,两者都在环内。以环入口为基准,它们的位置分别是模 的 和 。
概念视角几何
在圆周上追赶
两个指针都进入环之后,把间距定义为快指针领先慢指针的链接数,并取模 。每次迭代,快指针走两条链接,慢指针走一条,所以间距恰好增加一。在第 次迭代,间距是 ;间距回到零时,两个指针恰好相遇。
定理 2.2.2
(检测与相遇时间)
对有限的无环结构,循环以 null 结束。若可到达环,尾长为 、环长为 ,则循环恰好在 次迭代后返回环上一个节点,其中 是不小于 的最小正的 倍数。特别地,,所以检测需要 时间和 指针存储。
证明
(两个指针恰在环长的倍数时重合)
设 。若 ,慢指针仍在尾部、入口之前的节点,而尾部的每个节点都不同于环上的每个节点,所以若快指针在环内,两者不可能相等。若快指针也在尾部,它离 head 有 条链接,慢指针只有 条,而 ,所以两者是不同节点。因此在 之前不会相遇。
当 ,两个指针都在环内,以入口为基准,位置分别是模 的 和 。两者重合当且仅当 ,即
在 或之后必定存在 的某个正倍数,因此检测必定终止,首次相遇的时间就是最小的这样的倍数。若 ,它是 而不是零,因为算法在移动之后才作检查。这个倍数至多是 : 时等于 ; 时, 的倍数彼此相隔 ,所以有一个落在 内。因此工作量是 ,只存储两个指针。
定理 2.2.3
(找出入口)
设指针在 次迭代后相遇,。把其中一个指针留在相遇节点,并把另一个重置到 head。若两者每步前进一条链接,它们恰好在 步后首次相遇,相遇的节点就是入口。
证明
(相遇节点距入口在环内还差 步)
相遇时慢指针走了 条链接,所以相遇节点相对于入口的位置是 。再走 步,它的位置是 ,即入口。被重置到 head 的指针恰好走 条链接到达入口。因此两者在 步后都在入口。
它们不可能更早相遇。在走完 步之前,被重置的指针仍在环外,而另一个指针始终在环内,尾部节点不同于环上任何节点。当 时,两者一开始已在入口,不需要额外移动。
证明透视
为何相遇节点能指向入口
证明依赖一个量,就是尾长 。条件 来自相遇规则,它把相遇位置变成模 的 ,这只取决于尾长。所以从相遇节点再走 步会落在入口,而从 head 走同样 步也落在入口。第二阶段两个指针必须等速:否则两次行走到达时就不会都是 条链接。首次相遇的唯一性来自尾部在环之外。注意相遇节点本身并不直接说明入口在哪里:说明入口的是两段长度相同的行走,下面的追踪就是一例。
3. 完整的追踪示例
例题 2.2.4
(两个节点的尾部与四个节点的环)
设 A → B → C → D → E → F → C。这里 ,。记录每次检测迭代后的指针位置:
| 迭代次数 | slow | fast |
|---|---|---|
| 1 | B | C |
| 2 | C | E |
| 3 | D | C |
| 4 | E | E |
相遇点是 E,而不是 C。把一个指针重置到 A,另一个留在 E。走一步后它们分别位于 B,F;走两步后位于 C,C,即入口。若要单独测量环的长度,可让一个指针停在 C,沿 next 前进直到回到 C,共计四个链接。仅凭任意相遇节点的值或地址就推断 是不正确的。
反例模式
相遇节点就是入口
一个诱人的说法是:slow 与 fast 相遇的节点就是环的第一个节点。在上面的追踪中,相遇节点是 E,入口却是 C,在环内相差两条链接。事实上,相遇位置相对于入口是模 的 ,即 ,它非零是因为 不是 的倍数。只有当 整除 (例如 )时,这个说法才成立。修正的程序是把一个指针重置到 head,两者每步前进一条链接,第二次相遇的节点就是入口。
例题 2.2.5
(环从头节点开始)
设 A → B → C → A,所以 、。两个指针都从 A 开始:
| 迭代 | slow | fast |
|---|---|---|
| 1 | B | C |
| 2 | C | B |
| 3 | A | A |
首次相遇在第 次迭代,节点是入口 A;迭代次数是 而不是 ,因为相等只在移动之后检查。由于 ,两个指针本来就在入口上,重置阶段不需要任何步骤。对自环 A → A,第一次迭代后 slow 与 fast 都在 A:相遇在 。
例题 2.2.6
(无环链表与 null 检查)
空链表的 head 为 null,循环不会开始,返回 null。对 A → null,循环条件 fast.next != null 立即不成立,返回 null。对 A → B → null,第一次迭代把 slow 移到 B、fast 移到 null;slow == fast 为假(B 不是 null),之后循环条件不成立。对 A → B → C → null,第一次迭代得 B 和 C,循环条件 fast.next != null 在 C 处不成立。每种情形下算法都返回 null,而不会解引用 null 指针,因为先测试 fast 才测试 fast.next。
4. 若题目要求断开环
定位入口之后,从入口出发放置一个指针并不断前进,直到它的 next 指回入口。这个节点就是环中的前驱节点;只需把它的 next 改为 null。对于自环,前驱节点就是入口本身。原先可达的全部 个节点仍然各自恰好可达一次,且保持原来的首次访问顺序。只有当调用者拥有这些链接并明确需要一个线性链表时,这种修改才是合适的。检测例程与入口定位例程本身不会修改任何链接。
检查清单。 说明结构是有限且稳定的这一假设,并比较节点身份。在解引用之前检查 null。区分相遇点与入口,用模意义下的位置论证重置步骤,并在说明时间复杂度时同时计入非环前缀和环本身。不要声称单次运行就能证明链接在并发修改的结构上的行为。
习题与解答
快速检查
(对 A → B → C → D → B 追踪 Floyd 检测。给出 和 、相遇节点、相遇的迭代次序,以及重置阶段找到的节点。)
解答 · 答案
入口是 B,所以 、(环为 B, C, D)。各次迭代后的指针:第 1 次,slow B、fast C;第 2 次,slow C、fast B;第 3 次,slow D、fast D。它们在第 次迭代于 D 相遇,这是不小于 的最小正的 的倍数。把一个指针重置到 A,另一个留在 D。走一步后两者都在 B,所以重置阶段在 步后找到入口 B。
快速检查
(某链表的尾长 ,环长 。指针在第几次迭代相遇?相对于入口在哪个位置?)
解答 · 答案
相遇的迭代是不小于 的最小正的 的倍数,即 。慢指针走了 条链接,所以它在入口之后 个节点处。这与 一致。其后重置阶段正好需要 步到达入口。
快速检查
(在 A → B → C → D → B 上,Floyd 算法找到入口 B 之后,如何断开环使链表成为线性?结果是什么?)
解答 · 答案
从 B 放一个指针并向前推进,直至它的 next 是 B。B.next 是 C,C.next 是 D,D.next 是 B,所以 D 是环中的前驱节点。把 D.next 设为 null,得到线性链表 A → B → C → D → null,四个节点仍然各恰好可到达一次。