刷题软件上关于“环形链表 II”的题解一搜一大把，但每次面试聊到这道题，能写对代码的人不少，能把“两个阶段为什么成立”讲清楚的人寥寥无几。我自己刷题和面试别人的过程中，对这道题感触很深：它其实不是一道纯粹的链表题，而是一道“链表遍历 + 数学推导 + 复杂度意识”的组合题，尤其是题目里那句“不要使用额外空间”，直接把难度拉高了一个台阶。
这篇文章会用最通俗的方式拆解环形链表 II 的多种实现思路，重点讲清楚两种主流解法：哈希表方案和快慢指针方案，并把快慢指针背后的数学推导掰开揉碎讲明白。无论你是刚开始刷 LeetCode 的新手，还是准备校招/社招需要系统复盘链表题的选手，这篇文章都能帮你在面试时把这道题讲得比题解更透。
1. 先把 142 拆开：题目其实考了三件事
很多人第一次看这道题，以为它只是“判断链表有没有环”的升级版，多返回一个节点而已。实际上，这道题把三个独立的考察点叠在了一起。
1.1 一个 O(1) 空间限制把题目分成两个阶段
原题描述很简单：给定一个链表的头节点 head，返回链表开始入环的第一个节点。如果链表无环，则返回 null。注意题目中一般会标注“进阶：尽量不要使用额外空间”。
这句话就是分水岭。
如果你只求“能做出来”，那哈希表方案三分钟就能写完：遍历链表，把每个节点放进 set，遇到重复就返回。整个思路非常直觉，代码也不容易出错。但如果你把进阶要求当成必须满足的条件，就必须进入第二阶段思考：如何在常数空间内完成“找入口”这个任务。这正是环问题里最经典的数学部分。
所以在我看来，环形链表 II 的正确打开方式是分成两步走：第一步判断链表是否有环，第二步在已知有环的情况下定位入口节点。两步缺一不可。判断有环可以用快慢指针完成，定位入口则需要额外的推导。
1.2 哈希表能过，但面试官为什么不满意
很多候选人写完哈希表解法后都很自信，因为代码能在 O(n) 时间内通过所有测试用例，逻辑也没问题。但一旦面试官追问“能不能不用额外空间”，场面就开始尴尬了。
面试官不是不喜欢哈希表，而是这道题的核心考察点在于“你是否知道更优解”。链表题在面试中出现，本身就意味着考察空间复杂度的控制能力。链表不像数组那样可以随机访问，很多操作天然依赖 O(n) 的遍历，如果动不动就开一个哈希表来辅助，那数据结构的空间优势就谈不上。所以，能用 O(1) 空间解决环检测问题，才是这道题真正的考点。
1.3 这道题在算法面试里的真实定位
从面试角度来看，142 是一道非常典型的“中档偏上”题。它不像动态规划那样需要大量刷题积累，也不像并查集那样冷门，它的知识链路非常清晰：
- 数据结构基础：链表的遍历、节点引用
- 经典算法：Floyd 判圈算法
- 数学能力：通过路程关系推导入口位置
- 工程素养：处理空指针、处理边界条件
一个候选人如果能把这道题完整写出来，并且把“为什么第二次相遇在入口”讲清楚，基本上可以说明他具备扎实的链表基本功和一定的逻辑表达能力。这也就是为什么很多大厂面试喜欢把它当作二面算法题的原因。
2. 哈希表方案：五分钟写完，但别急着提交
哈希表方案是环形链表 II 最容易理解的解法。它的思路可以用一句话概括：路过的每个节点都记下来，如果发现有节点是第二次经过，那它就是环的入口。
2.1 哈希表的完整实现（Python）
先直接看代码：
def detectCycle(head): visited = set() cur = head while cur: # 当前节点已经在集合中，说明第二次到达该节点 if cur in visited: return cur visited.add(cur) cur = cur.next # 遍历到 null，说明链表无环 return None这里有个细节值得注意：我们是先判断cur in visited，再把节点加入集合。如果把顺序写反，比如先add再判断，那第一次访问的节点也会被当成“重复节点”，整个逻辑就错了。这种顺序问题是新手最常犯的低级错误。
2.2 为什么是“节点”而不是“值”
有些刚入门的朋友会疑惑：为什么要把节点放进 set，而不是把节点的值放进去？答案是链表中可能出现值相同但地址不同的节点。
比如一个链表包含两个值为 3 的节点，它们属于不同的对象。如果只存值，第二次遇到另一个值为 3 的新节点时会误判成环。因此必须保存节点引用本身，用对象身份来区分是否是同一个节点。
在 Python 里，默认情况下对象是可哈希的，set 会按照id(obj)来去重，所以直接存节点没问题。在 Java 中，HashSet 同样基于对象引用去重，也可以直接存节点对象，不需要重写 hashCode 和 equals 方法。
2.3 哈希表方案的加分用法
说实话，哈希表方案的代码量比快慢指针小得多，也容易解释。在面试中直接给出快慢指针当然最好，但如果你一时紧张忘了推导，先写出哈希表解法，再主动提“这个方案空间复杂度是 O(n)，我可以优化到 O(1)”，面试官通常不会直接让你挂。
关键在于：别把哈希表解法当成终点，要把它当成一种“兜底方案”。我在实际面试别人时，更看重候选人是否能在给出第一版后主动分析复杂度，并尝试提出改进思路。
3. 快慢指针阶段一：在环里追上才算证明有环
快慢指针方案，正式名称是 Floyd 判圈算法。它的第一步是判断链表是否有环，这一步完全不需要数学推导，代码也容易理解。
3.1 Floyd 判圈算法过程
整个算法分两个阶段：
- 阶段一：慢指针 slow 每次移动一步，快指针 fast 每次移动两步，两者都从 head 出发。如果 fast 先走到 null，说明链表无环；如果 slow 和 fast 在某个节点相遇，说明链表有环。
- 阶段二：让 slow 回到 head，fast 留在相遇点不动。然后两个指针都每次移动一步，当它们再次相遇时，相遇节点就是环的入口。
阶段二就是整道题的精髓。先看阶段一的 Python 代码：
def hasCycle(head): slow = head fast = head while fast and fast.next: slow = slow.next fast = fast.next.next if slow == fast: return True return False这里while fast and fast.next的条件非常关键。因为 fast 一次走两步，如果链表的最后一个节点指向 null，那么fast.next可能为 null，下一步就无法继续移动了。把条件写错，最容易出现空指针异常。
3.2 为什么 fast 一定会追上 slow
很多人对“一定会相遇”这个结论将信将疑，直觉上觉得 fast 可能绕了一圈又一圈就是碰不到 slow。实际上，只要链表有环，相遇是必然的。
可以这样理解：当 slow 也进入环之后，环就相当于一个圆形跑道。以慢指针为参照物，fast 相对于 slow 的速度是“每回合 1 步”。也就是说，fast 在逐回合地逼近 slow。由于跑道是封闭的，无论初始距离是多少，只要相对速度不为 0，且相对位移方向不变，最终一定能追上。
这个推理在数学上是严格的：设 slow 刚进入环时，fast 在它前方 x 步（在环内，x 小于环长 L）。每回合 fast 与 slow 的距离减少 1 步，最多 x 回合后必然相遇。正因为 x 是有限的，相遇一定发生。
3.3 fast 每次走 2 步，真的没有更好的选择吗
面试中经常有候选人问：快指针能不能走 3 步、4 步，走快点不是效率更高吗？
这个问题值得认真想一下。fast 走 3 步的话，相对速度为 2 步每次，确实也能追上 slow，理论上没错。但问题在于，一旦 fast 走得太快，它可能在某一回合“越过” slow 所在的位置，造成一种视觉上“明明同一条线却没碰头”的错觉。虽然从相对运动的角度来说，多走几个回合还是能追上，但数学分析会复杂不少。
更重要的是，走 2 步是在工程复杂度与数学简洁性之间最好的平衡点。2 步让相对速度为 1，推导入口位置时只需考虑最简单的整圈关系。所以刷题时别去追求“更快的快指针”，老老实实走 2 步是标准答案。
4. 快慢指针阶段二：入口是怎么被数学算出来的
如果说阶段一是“背代码”，那阶段二就是“考推导”。这部分的数学并不难，难的是你愿不愿意静下心来推一遍。
4.1 假设与变量定义
为了方便推导，先定义三个变量：
- a：从链表头节点到环入口节点的距离
- b：从环入口节点到 slow 和 fast 第一次相遇节点的距离
- L：环的长度
- c：从相遇节点继续向前走到环入口节点的距离，即 c = L - b
需要注意，这里的环长 L、距离 b 等都是以“节点个数”为单位计算的。举例：如果环长 4，入口到相遇点是 1 个节点，那相遇点到入口的下一次到达就是走 3 次 next，所以 c = 3。
4.2 从路程关系推出 a 和 c 的关系
第一次相遇时，假设 slow 走了 s 步，fast 走了 2s 步。
slow 从 head 出发，走到相遇点一共走了 a + b 步。因为 slow 刚进环不久，在第一圈内就被 fast 追上了，所以 b < L，这个前提很重要，后面会解释为什么一定成立。
fast 从 head 出发，沿环至少跑了一圈后来追上 slow。假设 fast 在环内比 slow 多跑了 k 圈（k >= 1），那 fast 的总路程是 a + b + kL。
于是有：
2(a + b) = a + b + kL
两边同时减去 a + b，得到：
a + b = kL
移项：
a = kL - b = (k - 1)L + (L - b) = (k - 1)L + c
这个等式非常漂亮。它说明：从 head 到环入口的距离 a，等于从相遇点继续走到环入口的距离 c，再加上整数倍的环长。
因此，如果让一个指针从 head 出发，另一个指针从相遇点出发，两者每次都走一步，那么走 a 步后，第一个指针正好到入口；第二个指针走 a 步，等价于绕了 (k - 1) 圈后再走 c 步，也正好到入口。所以两者第二次相遇的位置就是环入口。
4.3 为什么第二次“碰头”不会提前发生
细心的读者可能马上会追问：第二个指针在环里走着，第一个指针还在从 head 到入口的路上。如果第二个指针走 (k-1)L + c 步的过程中，第一个指针可能还没到入口，两个指针会不会在环入口之前就相遇？
答案是：不会。
原因很简单：在第一个指针到达入口之前，它还在链表的直线部分，根本没进入环。而第二个指针始终在环内。一个在环外，一个在环内，它们不可能提前相遇。只有当第一个指针刚进入环的那一瞬间，两者才有机会重合。而根据上面的路程关系，第二个指针在这个瞬间也恰好到达入口。
所以“第二次相遇点就是入口”这个结论，在逻辑上是闭环的。
顺带回答前面留下的问题：为什么第一次相遇时 slow 一定还没走满一圈？设 slow 刚进入环时，fast 在环内距离它最多 L - 1 步。由于 fast 相对 slow 每回合逼近 1 步，那么慢指针最多走 L - 1 步就会被追上，小于环长 L。所以 b < L 成立。
5. 多语言代码实现与本地验证
理论讲清楚了，代码就得跟上。这一节给出 Python 和 Java 的完整参考实现，以及本地构造测试用例的方法。
5.1 Python 完整解法（带注释）
from typing import Optional class ListNode: def __init__(self, x): self.val = x self.next = None class Solution: def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]: # 空链表或只有一个节点时肯定无环 if not head or not head.next: return None slow = head fast = head # 阶段一：找第一次相遇点 while fast and fast.next: slow = slow.next fast = fast.next.next if slow == fast: break # 如果 fast 走到了空，说明链表无环 if not fast or not fast.next: return None # 阶段二：一针从头走，一针从相遇点走 slow = head while slow != fast: slow = slow.next fast = fast.next return slow这个解法的关键是不要忘记if not fast or not fast.next这个判断。很多人写完阶段一后直接进入阶段二，结果遇到无环链表时 fast 已经是 null，一进入阶段二就直接空指针报错。
5.2 Java 解法与对象比较陷阱
Java 版本的思路完全一致，但有一个小坑需要提醒：链表节点比较一定要用引用比较，也就是slow == fast，不要用slow.val == fast.val。因为链表里可能存在值相同的节点，值相等并不代表是同一个节点。
public class Solution { public ListNode detectCycle(ListNode head) { if (head == null || head.next == null) { return null; } ListNode slow = head; ListNode fast = head; while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; if (slow == fast) { break; } } if (fast == null || fast.next == null) { return null; } slow = head; while (slow != fast) { slow = slow.next; fast = fast.next; } return slow; } }在 Java 里还要注意，ListNode默认的==比较的是引用地址，这正是我们想要的。别用equals()，因为如果没有重写，equals()在大多数时候也等价于引用比较，但一旦误写成比较 val，就会踩坑。
5.3 如何构造带环链表做本地测试
刷题时经常遇到一个尴尬：IDE 里没法像 LeetCode 那样直接传一个“带环链表”，不知道如何自测。这里分享一个简单的构造方法。
# 构造一个无环链表 a = ListNode(3) b = ListNode(2) c = ListNode(0) d = ListNode(-4) a.next = b b.next = c c.next = d # 为了让第 2 个节点成为环入口，让 d 指向 b d.next = b solution = Solution() result = solution.detectCycle(a) print(result.val) # 输出 2，符合预期这种构造方式就能模拟“环入口在第二个节点”的用例。测试时记得多切换几种形态：环入口在头节点、链表只有一个节点且自环、长链加长环，把这些边界都跑一遍，代码才算稳。
6. 高频变体与进阶追问：环长度、141、标记法
面试官不会只满足于你写出 142 本身。他大概率会顺着这道题往下追问几个变体，提前准备一下会非常加分。
6.1 环的长度怎么算
这是一个很自然的追问。当已经通过快慢指针找到第一次相遇点后，求环长度就非常简单：
def cycleLength(meetNode): cur = meetNode length = 1 while cur.next != meetNode: cur = cur.next length += 1 return length具体做法是：固定 slow 在相遇点，让另一个指针从相遇点出发，每次走一步，直到重新回到相遇点，走过的步数就是环长。
这里有个需要注意的边界：如果环中只有一个节点，也就是某个节点的 next 指向自己，循环应该立即结束，所以 length 的初始值设为 1 是必要的。也可以从cur.next != meetNode这个条件里看出来，这个写法天然覆盖了自环的情况。
6.2 只判环的 141 与 142 的代码差异
LeetCode 第 141 题问的是“是否存在环”，只需要返回 true 或 false。它其实就是 142 的截断版本，只需要阶段一，不需要阶段二。
def hasCycle(head): slow = head fast = head while fast and fast.next: slow = slow.next fast = fast.next.next if slow == fast: return True return False不少候选人做 142 时，会把 141 的代码直接搬过来，再强行挤进阶段二，结果越写越乱。我的建议是：先把 141 的空指针处理写好，再单独加阶段二，不要两题混在一起练。分开练能帮你把两个知识点的边界理清楚。
6.3 面试追问：能否修改链表结构
还有一种不太常规但偶有面试官会提的思路：遍历链表时，把每个访问过的节点的 next 指向自己或者指向某个固定哨兵节点。如果后续还能再遇到一个“已被标记”的节点，说明回到了起点，该节点就是环入口。
这种方案的空间复杂度是 O(1)，但会破坏链表结构，不满足“不要修改链表”的约束。面试官抛出这个问题时，通常是想考察你是否具备“通过变更数据换取空间复杂度”的意识。你可以先指出它能做到 O(1) 空间，再说它的致命缺点：破坏输入数据，工程上一般不接受，而且对只读链表不可行。这样回答既展示了思路广度，也体现了工程判断力。
7. 常见错误与排查经验速查
最后整理一份我在实际调试和面试点评中遇到频率最高的错误清单，都是实打实的踩坑经验。
7.1 空指针与死循环
以下两个错误是刷题新手最常犯的：
while fast.next:而不是while fast and fast.next:。如果 fast 本身已经是 null，再访问fast.next会直接抛异常。- 阶段二忘记重置 slow 到 head。直接从相遇点继续走，两个指针永远一起移动，永远相等，返回的节点完全错误。
我的建议是，代码写完后，先手动走一遍最小的用例：一个节点的链表，或两个节点成环的链表。这些极端用例能快速暴露空指针问题。
7.2 用值比较代替对象比较
有些语言对对象比较比较严格，有些则容易让新手混淆。比如 Java 中Integer的==在 -128 到 127 之间可能有特殊的缓存行为，这会让人误以为“值相等就是对象相等”。但在链表节点这种场景中，一定要坚持引用比较。
推荐在脑海中对齐一个原则：链表里判断“同一个节点”，看的不是val，而是“还是不是当初那个对象”。哪怕两个节点的值都是 5，只要地址不同，就是两个完全不同的节点。
7.3 复杂度、写法规范与面试表达要点
时间复杂度是 O(n)，空间复杂度是 O(1)，这是标准结论。但很多候选人在解释复杂度时会含糊其辞，只背结论不解释过程。
面试时可以这样表达：slow 进入环之前，两个指针都在链表的直线部分移动，这一步最多走 O(n) 步；slow 进入环后，fast 最多再走 L 步就能追上 slow，这里的 L 是环长，小于 n；阶段二同样最多走 O(n) 步，所以整体时间复杂度是 O(n)，空间上只用了两个指针变量，所以是 O(1)。
写代码时还有一个小规范：不要在一行里把所有变量都声明完，也不要写一堆没用上的临时变量。链表题本来就容易绕，变量越少，思路越清晰。
个人经验是：环形链表 II 这道题，代码量只有二十行出头，但值得你花两小时把第 4 节那段推导完整写一遍。我面试过不少候选人，能默写出快慢指针代码的人很多，能顺手画出a = (k-1)L + c的人很少。而后者往往就是面试官心里给你加分的关键。
最后分享一个小技巧：把环想象成操场跑道，慢指针是散步的人，快指针是跑步的人。第一次碰头只能证明你俩在同一片场地，想找到“入口”，得用路程差算出那个唯一的入场点。这个画面感建立起来之后，这道题基本就长在你脑子里了。
