先从一道我印象很深的机试题说起。某次我在后台帮忙评审一批应届生的机试答卷题目就是判断单链表是否有环。卷子收上来之后我发现一个现象能写出快慢指针的人不少但能完整解释两个指针为什么一定会相遇环入口怎么定位的人大概只有五分之一。更让人觉得可惜的是很多人明明代码写对了却因为循环条件里遗漏 fast 空指针判断在无环用例上直接崩溃整个题目的分全部丢掉。这道题之所以在机试里出现频率这么高是因为它表面上只考一个双指针技巧实际上却把链表建模、循环边界、复杂度分析、数学推导全部串在了一起。如果你只是背过答案很难在机试这种高压力环境下完整拿分。这篇文章我就把这道题的完整链路拆开讲从哈希表法到 Floyd 判圈算法从数学原理到边界坑再到环入口定位和常见的变体题希望能帮你把这道送分题变成真正稳拿的分。1. 为什么机试偏爱单链表判环它的考察面比想象中宽1.1 出题人到底在考什么先还原一下这道题的常见形态。函数式机试中题目一般给出链表的头节点 head要求你返回一个布尔值输入head [3, 2, 0, -4]环的入口在下标 1 输出true 输入head [1, 2]无环 输出false我做过几年技术面试官也参与过机试题目库的维护从出题人的视角看这道题被反复选中的原因有三层。第一层是数据结构基本功。链表节点的定义、指针的移动、空指针的判断这些基础不过关的人哪怕思路对代码也写不利索。第二层是算法思维。暴力法和哈希表法谁都能马上想到但如何在 O(1) 额外空间内完成检测就需要对双指针技巧有真正的理解。机试最有意思的地方就在这里——大多数题目会明确或隐式地要求空间的低消耗如果只给出哈希表解法往往只能拿到基础分。第三层是问题变形的潜力。有环本身只是一个状态接下来可以被追问环的入口在哪里、环有多长、两个链表是否相交每一次追问都要建立在同一个数学模型上。所以机试里它不是一个孤立题目而是一组题目的地基。1.2 从一次真实评审看到的普遍问题那次评审给我印象最深的有三份卷子。第一份用哈希表写出了正确结果时间复杂度没问题空间 O(n)题目在成绩单上标注了基础分不扣优化空间未答。第二份快慢指针思路全对却在 while 条件里直接访问了 fast-next没有先判断 fast 是否为空无环用例直接段错误。第三份更可惜代码正确但注释写得含糊后续问答题里问如果存在环如何找到入口他列了公式却无法解释每一步推导最终分被扣掉一半。机试和笔试不一样的地方在于它不仅要看最终答案还要看你在边界面前的容错能力。判环这块的坑就藏在那些看起来永远遇不到的地方后面我会专门用一章来展开。2. 从暴力法和哈希表法起步先保证做对再讨论做优2.1 为什么暴力法在机试里不靠谱我见过有同学在现场提出一种暴力解法维护一个计数器最多遍历 N 次如果还没走到 null就认为有环。这种思路的错误很明显——链表的长度 N 在机试里往往是未知的如果题目给的链表确实很长又无环这个计数器上限只会造成两种结果要么提前误判要么超时。还有一种更粗糙的做法把遍历过的节点地址打印出来人眼判断是否重复。这在本地调试时偶尔能用但在机试环境下显然不具备可执行性。所以暴力法基本只适合用来理解问题不是正式答案。2.2 哈希表法最自然的解法哈希表法的思路非常直观每走过一个节点就把这个节点的地址/引用存到哈希集合里。如果某个节点在集合中已经出现过说明链表存在环因为链表节点只有一个 next 指针能够回到一个已经访问过的节点一定是绕了一个圈。Python 的实现长这样def has_cycle(head): seen set() cur head while cur: if cur in seen: return True seen.add(cur) cur cur.next return False时间复杂度 O(n)空间复杂度 O(n)。这个方法最大的优点是几乎不会写错它把判环直接翻译成了判重复逻辑上没有任何弯弯绕绕。我经常建议面试准备期的同学把这个解法当作第一反应但接下来必须继续往下想如果要求额外空间 O(1)该怎么办。2.3 哈希表在机试中的隐性风险除了空间复杂度超标哈希表法还有一个很多人没意识到的隐患它依赖语言对对象哈希的正确实现。以 Python 为例节点的 hash 默认基于 id也就是内存地址机试环境下基本不会出问题。但如果链表节点是自定义对象并且你重写了eq而没有正确处理hash那集合去重逻辑就会变得不可预测。C 里如果要用 unordered_setListNode*指针哈希一般没问题但如果你把值存进去而不是地址就会把两个不同节点但值相同的链表误判成环。所以在机试里哈希表法的定位应该是用来兜底的正确答案而不是最优答案。如果题目有时间限制而你一时间写不出快慢指针先交一版哈希表法拿基础分再回头优化这是完全合理的应试策略。我个人的习惯是在本地调试时也先用哈希表法验证诉求再去验证快慢指针能更快定位问题。我把三种判环方法的整体对比先放在这里后面的章节会逐一展开方法时间复杂度空间复杂度能否定位入口主要风险暴力计数O(n)O(1)不能依赖链表长度上限不可靠哈希表O(n)O(n)可以记录入口空间可能超出限制快慢指针O(n)O(1)可以循环边界易写错3. Floyd 判圈算法快慢指针的标准解法与为什么详解3.1 基本思路一个在环里绕圈的模型Floyd 判圈算法是判环的标准解核心就一句话慢指针 slow 每次走一步快指针 fast 每次走两步从 head 同时出发。如果链表没有环fast 会先到达 null循环正常结束。如果有环slow 和 fast 最终一定会在环内相遇。用生活化的比喻来理解两个人在圆形操场上跑步一个人速度是另一个人的两倍。只要跑道是闭合的速度快的人从后面追上速度慢的人只是时间问题如果跑道不是闭合的速度快的人会先跑出跑道比赛自然结束。这个比喻能帮我们建立直觉但机试问答题不会只满足于直觉。面试官一定会追问为什么快指针每次走两步而不是三步为什么一定能追上3.2 为什么快指针走两步而不是三步、四步从能否追上的角度看只要 fast 比 slow 快也就是相对速度大于零理论上在环里迟早会追上。快指针每次走 k 步k 1等价于每单位时间让两者之间的距离缩短 k-1 步在环上无论初始差距是多少最终会差距变成环长的整数倍也就是追上。那为什么经典算法选 2 而不是 3 或 4两个原因。第一实现上的安全性快指针每次走两步循环条件只需要判断 fast 和 fast.next 是否为空再多走一步就要再多判断一层空指针代码更容易出错。第二效率上的考量进入环之前fast 已经比 slow 多走了一段距离如果步长过大fast 进入环后可能直接越过 slow 在环外的那一段导致需要多绕很多圈才能相遇最坏情况下反而增加时间消耗。两步是证明简单、实现安全、效率合适的经典平衡点机试里不要自作聪明去改成三步。3.3 相遇过程的严格推导现在来做机试中最容易卡住人的部分。假设从头节点到环入口的距离是 a 步环的周长是 b 步从环入口开始沿着 next 方向走到第一次相遇点的距离是 c 步。slow 到达环入口时已经走了 a 步而 fast 已经提前进入了环。由于 fast 比 slow 快一倍在 slow 进入环后的某个时间点fast 会从后面追上 slow。设追上时 slow 总共走了 S_slow 步fast 总共走了 S_fast 步。slow 在自己进入环之后没有绕多余的圈严格说在追上之前它一直在第一圈内所以S_slow a cfast 在追上 slow 之前一定比 slow 多绕了若干圈设多绕的圈数是 nn ≥ 1那么S_fast a c n * b又因为 fast 速度是 slow 的两倍相同时间内S_fast 2 * S_slow代入得到a c n * b 2 * (a c)整理一下n * b a c也就是a n * b - c这个等式非常关键。它说明从相遇点再走 a 步等于在环上绕了 n 圈后回到入口附近再退后 c 步也就是恰好回到环的入口。这在下一章找入口时会直接用。3.4 完整代码实现Python 版def has_cycle(head): slow head fast head while fast and fast.next: slow slow.next fast fast.next.next if slow is fast: return True return FalseC 版bool hasCycle(ListNode *head) { ListNode *slow head, *fast head; while (fast fast-next) { slow slow-next; fast fast-next-next; if (slow fast) return true; } return false; }注意循环的顺序先移动再比较。如果把比较放在移动之前初始状态下 slow 和 fast 都指向 head会被误判为有环这是新手最容易踩的坑。4. 进阶追问找到环的入口节点4.1 一道送分题如何变成拉分题机试最常见的升级问法是如果链表有环请返回环的第一个节点否则返回 null。很多同学能写出快慢指针判环却在这一步卡住。在第一次相遇发生时我们已经掌握了两个关键信息相遇点距离环入口的距离是 c且从相遇点继续走 a 步会回到环入口链表头到环入口的距离也是 a。结合上一章的公式 a n * b - c可以这样推导从相遇点出发走 a 步相当于先走到环入口再绕环走 n*b - c 步因为绕环整数圈后位置不变所以最终会回到环入口。而从 head 出发走 a 步同样到达环入口。所以算法非常优雅第一次相遇后把一个指针移回 head另一个指针留在相遇点两个指针每次都走一步它们相遇的位置就是环入口。4.2 入口定位的代码实现Python 版在 has_cycle 的基础上扩展def detect_cycle(head): slow head fast head while fast and fast.next: slow slow.next fast fast.next.next if slow is fast: # 相遇开始找入口 ptr1 head ptr2 slow while ptr1 is not ptr2: ptr1 ptr1.next ptr2 ptr2.next return ptr1 return NoneC 版ListNode *detectCycle(ListNode *head) { ListNode *slow head, *fast head; while (fast fast-next) { slow slow-next; fast fast-next-next; if (slow fast) { ListNode *p1 head, *p2 slow; while (p1 ! p2) { p1 p1-next; p2 p2-next; } return p1; } } return nullptr; }我建议你在机试前把这一段默写三遍以上。它不复杂但如果你在现场临时推导很容易因为紧张在ptr1 还是 ptr2 该留原地上弄混。记住口诀相遇之后一个从头走一个从相遇点走速度都是 1第一次见面就是入口。4.3 一个额外的小证明为什么相遇点一定在环内有同学会问如果链表很长环很小会不会相遇点在环外答案是不会。fast 比 slow 早进入环在 slow 还没进入环之前fast 已经在环内绕圈了。慢指针进入环后fast 绝不会回到环外的直线上因为环出口不存在——单链表的 next 方向是唯一的进入环后就不可能再跳回环前面的节点了。所以第一次相遇一定发生在环内。5. 机试实战从输入构造到完整提交5.1 输入格式与带环链表构造很多机试平台给的输入不是一个现成的链表对象而是类似这种格式输入head [3, 2, 0, -4], pos 1意思是从下标 1 的节点开始成环也就是尾节点的 next 指向下标为 1 的节点。如果 pos -1表示无环。本地调试时我们可以写一个工具函数来构造这种带环链表class ListNode: def __init__(self, val0, nextNone): self.val val self.next next def build_linked_list(vals, pos): if not vals: return None headers [ListNode(v) for v in vals] for i in range(len(headers) - 1): headers[i].next headers[i 1] if pos 0: headers[-1].next headers[pos] return headers[0]这样你就可以在本地用同样的输入格式测试全部算法不会因为构造链表的方式不统一而浪费时间。5.2 这道题最容易翻车的五个边界我在评审和辅导中总结了五个最容易翻车的边界每一个都真实见过有人因此丢分。第一空链表。head 为 null 时函数返回 false 即可。很多人在循环条件里没考虑直接访问 head.next一上来就崩溃。第二单节点无环。节点只有一个next 为 null循环正常结束返回 false。这一般不会出错出错的是单节点自环也就是节点的 next 指向自己循环条件 fast 和 fast.next 都不为空移动之后 slow 和 fast 都指向同一个节点返回 true这个判断不能写漏。第三环入口就在头节点。比如链表只有一个节点且自环或者首节点就成环的情况。入口定位代码里ptr1 和 ptr2 最初分别在 head 和相遇点如果相遇点恰好就是 headwhile 循环不会进入直接返回 head这是正确的。第四无环链表非常长。快指针每次走两步最后一次移动前 fast 可能指向倒数第二个节点此时 fast.next 不为空但 fast.next.next 为空。标准的 while fast and fast.next 条件会安全退出不会出现空指针解引用。第五使用哈希表法时如果把节点值当成去重依据遇到两个相同值的不同节点会错误地返回 true这是最隐蔽的逻辑 bug。只要记住必须去重的是节点地址不是节点值就能避开。5.3 提交前的自查清单我自己在机试前通常会给学员这样一份自查清单每道链表题都可以套用是否处理了空链表循环条件是否覆盖了 fast 本身为空和 fast.next 为空的两种情况移动和比较的顺序是否正确初始状态有没有造成误判是否在修改传入链表如果题目不允许快慢指针法天然不会修改链表这一点比标记法更讨喜。返回值类型是否匹配题目要求这份清单看似基础但机试现场紧张时最容易漏掉的就是第一和第二条。6. 踩坑记录与排查思路本地测对、交上去却错的典型案例6.1 一个典型的死循环排查过程我辅导过一位同学他的代码长这样bool hasCycle(ListNode *head) { ListNode *slow head; ListNode *fast head; while (fast ! nullptr) { slow slow-next; fast fast-next-next; if (slow fast) return true; } return false; }本地测了三个用例全对交上去之后部分用例超时。我们一步步排查。第一轮看代码逻辑发现 while 条件只判断了 fast 不为空没有判断 fast-next 是否为空。在每次迭代中如果 fast 已经走到最后一个节点fast-next 为空下一次访问 fast-next-next 就会解引用空指针。但很多编译环境下这并不会立刻崩溃而是会读到一块随机内存让程序陷入不可预期的状态最终表现为超时。确认原因后把循环条件改成 while (fast ! nullptr fast-next ! nullptr)问题就消失了。这个案例非常典型反映的其实是对快指针边界缺乏建模的问题。修完后我又让他写了一个单节点无环的用例跑一遍顺便检查了移动顺序有没有初始误判。6.2 另一个坑误把相等判断写成了值比较还有一个案例是用类 Java 语言写的他写的是if (slow.val fast.val) return true;这段代码在链表节点值恰好重复的情况下会误报有环。比如无环链表 [1, 2, 1, 3]快指针和慢指针可能同时停在值都为 1 的不同节点上于是返回了 true。正确做法是比较节点引用slow fast或者 Python 里用 slow is fast比较的是内存地址不是值。这也提醒我们判环问题判断的是同一个节点而不是相同的值。链表中节点值的重复是常态用值作为判据绝对不可取。6.3 为什么建议机试前专门练自环用例我顺便分享一个练习技巧。机试题目为了控制难度经常把环设置在链表尾部附近也就是尾节点指向中间某个节点。但你一定要专门构造一个单节点自环来测试因为这种形态最容易暴露循环条件错误。本地构造自环只需要node ListNode(1) node.next node build_linked_list([1], 0)自环用例能同时验证两件事判环是否返回 true以及 if slow is fast 的判断是否真的在移动后触发。如果你把比较放在移动之前自环用例会直接误判这个错误在普通用例上反而不容易看出来。7. 从判环延伸到两大高频变体题7.1 变体一如何计算环的长度如果已经找到环内某个节点环长就很容易求了。最直观的办法是在相遇点让一个指针原地不动另一个指针每次走一步再次回到相遇点时走过的步数就是环长。代码实现如下def cycle_length(head): meet_node detect_cycle(head) if not meet_node: return 0 cur meet_node.next length 1 while cur is not meet_node: cur cur.next length 1 return length有几个细节值得注意。第一必须从环内节点出发入口节点本身可以相遇点也可以。第二边界是绕一圈刚好回到起点计数从 1 开始表示已经算上起点本身。第三如果环长是 1自环节点cur 一开始就等于 meet_nodewhile 不进入length 保持 1结果正确。7.2 变体二判断两个单链表是否相交这实际上是一道非常经典的扩展题常规做法是遍历两个链表分别得到长度让长链表先走差值步然后两个指针同步走第一个相等的节点就是交点。但你有没有想过判环技巧也能用来做这道题一个很有启发性的做法是把链表 A 的尾节点接到链表 B 的头部然后对链表 B 判环。如果 A 和 B 存在交点那么连接之后 B 必然成环如果不存在交点B 依然是无环链表。这个方法把相交这个新型问题强行归约到了判环上非常适合作为面试时的思路拓展。当然实际机试中我更推荐常规长度差法因为它不修改任何链表。这个归约方法的价值在于帮你理解链表题的核心考点很少是孤立技巧而是你是否能在不同题型之间建立映射关系。7.3 标记法什么时候可以用还有一个思路是给节点增加访问标记比如把 val 改成一个特殊值或者引入 visited 字段。这个方法在理论课上常常被提到因为它直观且时间复杂度 O(n)空间 O(1)。但我几乎不推荐在机试中使用原因是它修改了输入数据平台可能在后续测试中反复使用同一个链表一旦节点被修改后续用例就会全部脏掉。快慢指针法不修改任何数据这才是更安全的通用解。8. 写在最后的一点实战体会判环这道题刷过的人都会背快慢指针但能把每一步原理讲清楚的人并不多。我自己的习惯是每道链表题写完代码之后至少在白板上画一遍三个点头节点、环入口、相遇点。把这三者的距离关系用 a、b、c 三个字母标出来很多问题就不需要死记硬背了。如果你现在正在准备机试我建议你按这个顺序练习先写哈希表法确保思路正确再写快慢指针法确保空间达标然后再写入口定位版本最后用一个自环节点和一个无环长链表做边界测试。整个过程大概半小时练完后你会对为什么循环条件要这样写为什么相遇后一个从头走一个从相遇点走有真正的肌肉记忆。曾经有一位学员在机试前一晚用这个方法练了十几遍第二天遇到的就是这道题的原题他选择题目的第二问写入口定位顺利通过。事后他跟我说最让他意外的是面试官居然追问了为什么快指针走两圈之内一定能追上慢指针他已经能把推导过程完整写出来了。这道题拿满分的关键从来不是知道答案而是能证明答案。最后再分享一个小技巧记录在这里如果你在机试现场实在推导不出入口公式可以直接用哈希表法返回入口节点。它空间复杂度高一些但至少能保证正确性。无论是拿满分还是拿基础分先把能得的分稳稳装进口袋里永远比追求最优解却因为边界问题挂掉更好。
单链表判环：快慢指针与Floyd判圈算法全解析
先从一道我印象很深的机试题说起。某次我在后台帮忙评审一批应届生的机试答卷题目就是判断单链表是否有环。卷子收上来之后我发现一个现象能写出快慢指针的人不少但能完整解释两个指针为什么一定会相遇环入口怎么定位的人大概只有五分之一。更让人觉得可惜的是很多人明明代码写对了却因为循环条件里遗漏 fast 空指针判断在无环用例上直接崩溃整个题目的分全部丢掉。这道题之所以在机试里出现频率这么高是因为它表面上只考一个双指针技巧实际上却把链表建模、循环边界、复杂度分析、数学推导全部串在了一起。如果你只是背过答案很难在机试这种高压力环境下完整拿分。这篇文章我就把这道题的完整链路拆开讲从哈希表法到 Floyd 判圈算法从数学原理到边界坑再到环入口定位和常见的变体题希望能帮你把这道送分题变成真正稳拿的分。1. 为什么机试偏爱单链表判环它的考察面比想象中宽1.1 出题人到底在考什么先还原一下这道题的常见形态。函数式机试中题目一般给出链表的头节点 head要求你返回一个布尔值输入head [3, 2, 0, -4]环的入口在下标 1 输出true 输入head [1, 2]无环 输出false我做过几年技术面试官也参与过机试题目库的维护从出题人的视角看这道题被反复选中的原因有三层。第一层是数据结构基本功。链表节点的定义、指针的移动、空指针的判断这些基础不过关的人哪怕思路对代码也写不利索。第二层是算法思维。暴力法和哈希表法谁都能马上想到但如何在 O(1) 额外空间内完成检测就需要对双指针技巧有真正的理解。机试最有意思的地方就在这里——大多数题目会明确或隐式地要求空间的低消耗如果只给出哈希表解法往往只能拿到基础分。第三层是问题变形的潜力。有环本身只是一个状态接下来可以被追问环的入口在哪里、环有多长、两个链表是否相交每一次追问都要建立在同一个数学模型上。所以机试里它不是一个孤立题目而是一组题目的地基。1.2 从一次真实评审看到的普遍问题那次评审给我印象最深的有三份卷子。第一份用哈希表写出了正确结果时间复杂度没问题空间 O(n)题目在成绩单上标注了基础分不扣优化空间未答。第二份快慢指针思路全对却在 while 条件里直接访问了 fast-next没有先判断 fast 是否为空无环用例直接段错误。第三份更可惜代码正确但注释写得含糊后续问答题里问如果存在环如何找到入口他列了公式却无法解释每一步推导最终分被扣掉一半。机试和笔试不一样的地方在于它不仅要看最终答案还要看你在边界面前的容错能力。判环这块的坑就藏在那些看起来永远遇不到的地方后面我会专门用一章来展开。2. 从暴力法和哈希表法起步先保证做对再讨论做优2.1 为什么暴力法在机试里不靠谱我见过有同学在现场提出一种暴力解法维护一个计数器最多遍历 N 次如果还没走到 null就认为有环。这种思路的错误很明显——链表的长度 N 在机试里往往是未知的如果题目给的链表确实很长又无环这个计数器上限只会造成两种结果要么提前误判要么超时。还有一种更粗糙的做法把遍历过的节点地址打印出来人眼判断是否重复。这在本地调试时偶尔能用但在机试环境下显然不具备可执行性。所以暴力法基本只适合用来理解问题不是正式答案。2.2 哈希表法最自然的解法哈希表法的思路非常直观每走过一个节点就把这个节点的地址/引用存到哈希集合里。如果某个节点在集合中已经出现过说明链表存在环因为链表节点只有一个 next 指针能够回到一个已经访问过的节点一定是绕了一个圈。Python 的实现长这样def has_cycle(head): seen set() cur head while cur: if cur in seen: return True seen.add(cur) cur cur.next return False时间复杂度 O(n)空间复杂度 O(n)。这个方法最大的优点是几乎不会写错它把判环直接翻译成了判重复逻辑上没有任何弯弯绕绕。我经常建议面试准备期的同学把这个解法当作第一反应但接下来必须继续往下想如果要求额外空间 O(1)该怎么办。2.3 哈希表在机试中的隐性风险除了空间复杂度超标哈希表法还有一个很多人没意识到的隐患它依赖语言对对象哈希的正确实现。以 Python 为例节点的 hash 默认基于 id也就是内存地址机试环境下基本不会出问题。但如果链表节点是自定义对象并且你重写了eq而没有正确处理hash那集合去重逻辑就会变得不可预测。C 里如果要用 unordered_setListNode*指针哈希一般没问题但如果你把值存进去而不是地址就会把两个不同节点但值相同的链表误判成环。所以在机试里哈希表法的定位应该是用来兜底的正确答案而不是最优答案。如果题目有时间限制而你一时间写不出快慢指针先交一版哈希表法拿基础分再回头优化这是完全合理的应试策略。我个人的习惯是在本地调试时也先用哈希表法验证诉求再去验证快慢指针能更快定位问题。我把三种判环方法的整体对比先放在这里后面的章节会逐一展开方法时间复杂度空间复杂度能否定位入口主要风险暴力计数O(n)O(1)不能依赖链表长度上限不可靠哈希表O(n)O(n)可以记录入口空间可能超出限制快慢指针O(n)O(1)可以循环边界易写错3. Floyd 判圈算法快慢指针的标准解法与为什么详解3.1 基本思路一个在环里绕圈的模型Floyd 判圈算法是判环的标准解核心就一句话慢指针 slow 每次走一步快指针 fast 每次走两步从 head 同时出发。如果链表没有环fast 会先到达 null循环正常结束。如果有环slow 和 fast 最终一定会在环内相遇。用生活化的比喻来理解两个人在圆形操场上跑步一个人速度是另一个人的两倍。只要跑道是闭合的速度快的人从后面追上速度慢的人只是时间问题如果跑道不是闭合的速度快的人会先跑出跑道比赛自然结束。这个比喻能帮我们建立直觉但机试问答题不会只满足于直觉。面试官一定会追问为什么快指针每次走两步而不是三步为什么一定能追上3.2 为什么快指针走两步而不是三步、四步从能否追上的角度看只要 fast 比 slow 快也就是相对速度大于零理论上在环里迟早会追上。快指针每次走 k 步k 1等价于每单位时间让两者之间的距离缩短 k-1 步在环上无论初始差距是多少最终会差距变成环长的整数倍也就是追上。那为什么经典算法选 2 而不是 3 或 4两个原因。第一实现上的安全性快指针每次走两步循环条件只需要判断 fast 和 fast.next 是否为空再多走一步就要再多判断一层空指针代码更容易出错。第二效率上的考量进入环之前fast 已经比 slow 多走了一段距离如果步长过大fast 进入环后可能直接越过 slow 在环外的那一段导致需要多绕很多圈才能相遇最坏情况下反而增加时间消耗。两步是证明简单、实现安全、效率合适的经典平衡点机试里不要自作聪明去改成三步。3.3 相遇过程的严格推导现在来做机试中最容易卡住人的部分。假设从头节点到环入口的距离是 a 步环的周长是 b 步从环入口开始沿着 next 方向走到第一次相遇点的距离是 c 步。slow 到达环入口时已经走了 a 步而 fast 已经提前进入了环。由于 fast 比 slow 快一倍在 slow 进入环后的某个时间点fast 会从后面追上 slow。设追上时 slow 总共走了 S_slow 步fast 总共走了 S_fast 步。slow 在自己进入环之后没有绕多余的圈严格说在追上之前它一直在第一圈内所以S_slow a cfast 在追上 slow 之前一定比 slow 多绕了若干圈设多绕的圈数是 nn ≥ 1那么S_fast a c n * b又因为 fast 速度是 slow 的两倍相同时间内S_fast 2 * S_slow代入得到a c n * b 2 * (a c)整理一下n * b a c也就是a n * b - c这个等式非常关键。它说明从相遇点再走 a 步等于在环上绕了 n 圈后回到入口附近再退后 c 步也就是恰好回到环的入口。这在下一章找入口时会直接用。3.4 完整代码实现Python 版def has_cycle(head): slow head fast head while fast and fast.next: slow slow.next fast fast.next.next if slow is fast: return True return FalseC 版bool hasCycle(ListNode *head) { ListNode *slow head, *fast head; while (fast fast-next) { slow slow-next; fast fast-next-next; if (slow fast) return true; } return false; }注意循环的顺序先移动再比较。如果把比较放在移动之前初始状态下 slow 和 fast 都指向 head会被误判为有环这是新手最容易踩的坑。4. 进阶追问找到环的入口节点4.1 一道送分题如何变成拉分题机试最常见的升级问法是如果链表有环请返回环的第一个节点否则返回 null。很多同学能写出快慢指针判环却在这一步卡住。在第一次相遇发生时我们已经掌握了两个关键信息相遇点距离环入口的距离是 c且从相遇点继续走 a 步会回到环入口链表头到环入口的距离也是 a。结合上一章的公式 a n * b - c可以这样推导从相遇点出发走 a 步相当于先走到环入口再绕环走 n*b - c 步因为绕环整数圈后位置不变所以最终会回到环入口。而从 head 出发走 a 步同样到达环入口。所以算法非常优雅第一次相遇后把一个指针移回 head另一个指针留在相遇点两个指针每次都走一步它们相遇的位置就是环入口。4.2 入口定位的代码实现Python 版在 has_cycle 的基础上扩展def detect_cycle(head): slow head fast head while fast and fast.next: slow slow.next fast fast.next.next if slow is fast: # 相遇开始找入口 ptr1 head ptr2 slow while ptr1 is not ptr2: ptr1 ptr1.next ptr2 ptr2.next return ptr1 return NoneC 版ListNode *detectCycle(ListNode *head) { ListNode *slow head, *fast head; while (fast fast-next) { slow slow-next; fast fast-next-next; if (slow fast) { ListNode *p1 head, *p2 slow; while (p1 ! p2) { p1 p1-next; p2 p2-next; } return p1; } } return nullptr; }我建议你在机试前把这一段默写三遍以上。它不复杂但如果你在现场临时推导很容易因为紧张在ptr1 还是 ptr2 该留原地上弄混。记住口诀相遇之后一个从头走一个从相遇点走速度都是 1第一次见面就是入口。4.3 一个额外的小证明为什么相遇点一定在环内有同学会问如果链表很长环很小会不会相遇点在环外答案是不会。fast 比 slow 早进入环在 slow 还没进入环之前fast 已经在环内绕圈了。慢指针进入环后fast 绝不会回到环外的直线上因为环出口不存在——单链表的 next 方向是唯一的进入环后就不可能再跳回环前面的节点了。所以第一次相遇一定发生在环内。5. 机试实战从输入构造到完整提交5.1 输入格式与带环链表构造很多机试平台给的输入不是一个现成的链表对象而是类似这种格式输入head [3, 2, 0, -4], pos 1意思是从下标 1 的节点开始成环也就是尾节点的 next 指向下标为 1 的节点。如果 pos -1表示无环。本地调试时我们可以写一个工具函数来构造这种带环链表class ListNode: def __init__(self, val0, nextNone): self.val val self.next next def build_linked_list(vals, pos): if not vals: return None headers [ListNode(v) for v in vals] for i in range(len(headers) - 1): headers[i].next headers[i 1] if pos 0: headers[-1].next headers[pos] return headers[0]这样你就可以在本地用同样的输入格式测试全部算法不会因为构造链表的方式不统一而浪费时间。5.2 这道题最容易翻车的五个边界我在评审和辅导中总结了五个最容易翻车的边界每一个都真实见过有人因此丢分。第一空链表。head 为 null 时函数返回 false 即可。很多人在循环条件里没考虑直接访问 head.next一上来就崩溃。第二单节点无环。节点只有一个next 为 null循环正常结束返回 false。这一般不会出错出错的是单节点自环也就是节点的 next 指向自己循环条件 fast 和 fast.next 都不为空移动之后 slow 和 fast 都指向同一个节点返回 true这个判断不能写漏。第三环入口就在头节点。比如链表只有一个节点且自环或者首节点就成环的情况。入口定位代码里ptr1 和 ptr2 最初分别在 head 和相遇点如果相遇点恰好就是 headwhile 循环不会进入直接返回 head这是正确的。第四无环链表非常长。快指针每次走两步最后一次移动前 fast 可能指向倒数第二个节点此时 fast.next 不为空但 fast.next.next 为空。标准的 while fast and fast.next 条件会安全退出不会出现空指针解引用。第五使用哈希表法时如果把节点值当成去重依据遇到两个相同值的不同节点会错误地返回 true这是最隐蔽的逻辑 bug。只要记住必须去重的是节点地址不是节点值就能避开。5.3 提交前的自查清单我自己在机试前通常会给学员这样一份自查清单每道链表题都可以套用是否处理了空链表循环条件是否覆盖了 fast 本身为空和 fast.next 为空的两种情况移动和比较的顺序是否正确初始状态有没有造成误判是否在修改传入链表如果题目不允许快慢指针法天然不会修改链表这一点比标记法更讨喜。返回值类型是否匹配题目要求这份清单看似基础但机试现场紧张时最容易漏掉的就是第一和第二条。6. 踩坑记录与排查思路本地测对、交上去却错的典型案例6.1 一个典型的死循环排查过程我辅导过一位同学他的代码长这样bool hasCycle(ListNode *head) { ListNode *slow head; ListNode *fast head; while (fast ! nullptr) { slow slow-next; fast fast-next-next; if (slow fast) return true; } return false; }本地测了三个用例全对交上去之后部分用例超时。我们一步步排查。第一轮看代码逻辑发现 while 条件只判断了 fast 不为空没有判断 fast-next 是否为空。在每次迭代中如果 fast 已经走到最后一个节点fast-next 为空下一次访问 fast-next-next 就会解引用空指针。但很多编译环境下这并不会立刻崩溃而是会读到一块随机内存让程序陷入不可预期的状态最终表现为超时。确认原因后把循环条件改成 while (fast ! nullptr fast-next ! nullptr)问题就消失了。这个案例非常典型反映的其实是对快指针边界缺乏建模的问题。修完后我又让他写了一个单节点无环的用例跑一遍顺便检查了移动顺序有没有初始误判。6.2 另一个坑误把相等判断写成了值比较还有一个案例是用类 Java 语言写的他写的是if (slow.val fast.val) return true;这段代码在链表节点值恰好重复的情况下会误报有环。比如无环链表 [1, 2, 1, 3]快指针和慢指针可能同时停在值都为 1 的不同节点上于是返回了 true。正确做法是比较节点引用slow fast或者 Python 里用 slow is fast比较的是内存地址不是值。这也提醒我们判环问题判断的是同一个节点而不是相同的值。链表中节点值的重复是常态用值作为判据绝对不可取。6.3 为什么建议机试前专门练自环用例我顺便分享一个练习技巧。机试题目为了控制难度经常把环设置在链表尾部附近也就是尾节点指向中间某个节点。但你一定要专门构造一个单节点自环来测试因为这种形态最容易暴露循环条件错误。本地构造自环只需要node ListNode(1) node.next node build_linked_list([1], 0)自环用例能同时验证两件事判环是否返回 true以及 if slow is fast 的判断是否真的在移动后触发。如果你把比较放在移动之前自环用例会直接误判这个错误在普通用例上反而不容易看出来。7. 从判环延伸到两大高频变体题7.1 变体一如何计算环的长度如果已经找到环内某个节点环长就很容易求了。最直观的办法是在相遇点让一个指针原地不动另一个指针每次走一步再次回到相遇点时走过的步数就是环长。代码实现如下def cycle_length(head): meet_node detect_cycle(head) if not meet_node: return 0 cur meet_node.next length 1 while cur is not meet_node: cur cur.next length 1 return length有几个细节值得注意。第一必须从环内节点出发入口节点本身可以相遇点也可以。第二边界是绕一圈刚好回到起点计数从 1 开始表示已经算上起点本身。第三如果环长是 1自环节点cur 一开始就等于 meet_nodewhile 不进入length 保持 1结果正确。7.2 变体二判断两个单链表是否相交这实际上是一道非常经典的扩展题常规做法是遍历两个链表分别得到长度让长链表先走差值步然后两个指针同步走第一个相等的节点就是交点。但你有没有想过判环技巧也能用来做这道题一个很有启发性的做法是把链表 A 的尾节点接到链表 B 的头部然后对链表 B 判环。如果 A 和 B 存在交点那么连接之后 B 必然成环如果不存在交点B 依然是无环链表。这个方法把相交这个新型问题强行归约到了判环上非常适合作为面试时的思路拓展。当然实际机试中我更推荐常规长度差法因为它不修改任何链表。这个归约方法的价值在于帮你理解链表题的核心考点很少是孤立技巧而是你是否能在不同题型之间建立映射关系。7.3 标记法什么时候可以用还有一个思路是给节点增加访问标记比如把 val 改成一个特殊值或者引入 visited 字段。这个方法在理论课上常常被提到因为它直观且时间复杂度 O(n)空间 O(1)。但我几乎不推荐在机试中使用原因是它修改了输入数据平台可能在后续测试中反复使用同一个链表一旦节点被修改后续用例就会全部脏掉。快慢指针法不修改任何数据这才是更安全的通用解。8. 写在最后的一点实战体会判环这道题刷过的人都会背快慢指针但能把每一步原理讲清楚的人并不多。我自己的习惯是每道链表题写完代码之后至少在白板上画一遍三个点头节点、环入口、相遇点。把这三者的距离关系用 a、b、c 三个字母标出来很多问题就不需要死记硬背了。如果你现在正在准备机试我建议你按这个顺序练习先写哈希表法确保思路正确再写快慢指针法确保空间达标然后再写入口定位版本最后用一个自环节点和一个无环长链表做边界测试。整个过程大概半小时练完后你会对为什么循环条件要这样写为什么相遇后一个从头走一个从相遇点走有真正的肌肉记忆。曾经有一位学员在机试前一晚用这个方法练了十几遍第二天遇到的就是这道题的原题他选择题目的第二问写入口定位顺利通过。事后他跟我说最让他意外的是面试官居然追问了为什么快指针走两圈之内一定能追上慢指针他已经能把推导过程完整写出来了。这道题拿满分的关键从来不是知道答案而是能证明答案。最后再分享一个小技巧记录在这里如果你在机试现场实在推导不出入口公式可以直接用哈希表法返回入口节点。它空间复杂度高一些但至少能保证正确性。无论是拿满分还是拿基础分先把能得的分稳稳装进口袋里永远比追求最优解却因为边界问题挂掉更好。
