先从一道我印象很深的机试题说起。某次我在后台帮忙评审一批应届生的机试答卷，题目就是"判断单链表是否有环"。卷子收上来之后我发现一个现象：能写出快慢指针的人不少，但能完整解释"两个指针为什么一定会相遇""环入口怎么定位"的人，大概只有五分之一。更让人觉得可惜的是，很多人明明代码写对了，却因为循环条件里遗漏 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_set<ListNode*>，指针哈希一般没问题，但如果你把"值"存进去而不是"地址"，就会把两个不同节点但值相同的链表误判成环。
所以在机试里，哈希表法的定位应该是"用来兜底的正确答案"，而不是"最优答案"。如果题目有时间限制而你一时间写不出快慢指针，先交一版哈希表法拿基础分，再回头优化，这是完全合理的应试策略。我个人的习惯是，在本地调试时也先用哈希表法验证诉求，再去验证快慢指针，能更快定位问题。
我把三种判环方法的整体对比先放在这里，后面的章节会逐一展开：
| 方法 | 时间复杂度 | 空间复杂度 | 能否定位入口 | 主要风险 |
|---|---|---|---|---|
| 暴力计数 | 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 + c
fast 在追上 slow 之前，一定比 slow 多绕了若干圈，设多绕的圈数是 n（n ≥ 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, val=0, next=None): 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 和相遇点，如果相遇点恰好就是 head，while 循环不会进入，直接返回 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_node，while 不进入，length 保持 1，结果正确。
7.2 变体二：判断两个单链表是否相交
这实际上是一道非常经典的扩展题，常规做法是遍历两个链表分别得到长度，让长链表先走差值步，然后两个指针同步走，第一个相等的节点就是交点。
但你有没有想过，判环技巧也能用来做这道题？一个很有启发性的做法是：把链表 A 的尾节点接到链表 B 的头部，然后对链表 B 判环。如果 A 和 B 存在交点，那么连接之后 B 必然成环；如果不存在交点，B 依然是无环链表。这个方法把"相交"这个新型问题强行归约到了"判环"上，非常适合作为面试时的思路拓展。
当然，实际机试中我更推荐常规长度差法，因为它不修改任何链表。这个归约方法的价值在于帮你理解：链表题的核心考点很少是孤立技巧，而是你是否能在不同题型之间建立映射关系。
7.3 标记法：什么时候可以用
还有一个思路是给节点增加访问标记，比如把 val 改成一个特殊值，或者引入 visited 字段。这个方法在理论课上常常被提到，因为它直观且时间复杂度 O(n)，空间 O(1)。但我几乎不推荐在机试中使用，原因是它修改了输入数据，平台可能在后续测试中反复使用同一个链表，一旦节点被修改，后续用例就会全部脏掉。快慢指针法不修改任何数据，这才是更安全的通用解。
8. 写在最后的一点实战体会
判环这道题，刷过的人都会背快慢指针，但能把每一步原理讲清楚的人并不多。我自己的习惯是，每道链表题写完代码之后，至少在白板上画一遍"三个点"：头节点、环入口、相遇点。把这三者的距离关系用 a、b、c 三个字母标出来，很多问题就不需要死记硬背了。
如果你现在正在准备机试，我建议你按这个顺序练习：先写哈希表法确保思路正确，再写快慢指针法确保空间达标，然后再写入口定位版本，最后用一个自环节点和一个无环长链表做边界测试。整个过程大概半小时，练完后你会对"为什么循环条件要这样写""为什么相遇后一个从头走一个从相遇点走"有真正的肌肉记忆。
曾经有一位学员在机试前一晚用这个方法练了十几遍，第二天遇到的就是这道题的原题，他选择题目的第二问写入口定位，顺利通过。事后他跟我说，最让他意外的是面试官居然追问了"为什么快指针走两圈之内一定能追上慢指针"，他已经能把推导过程完整写出来了。这道题拿满分的关键从来不是"知道答案"，而是"能证明答案"。
最后再分享一个小技巧，记录在这里：如果你在机试现场实在推导不出入口公式，可以直接用哈希表法返回入口节点。它空间复杂度高一些，但至少能保证正确性。无论是拿满分还是拿基础分，先把能得的分稳稳装进口袋里，永远比追求最优解却因为边界问题挂掉更好。
空间最优解)
