刷题软件上关于“环形链表 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 回到 headfast 留在相遇点不动。然后两个指针都每次移动一步当它们再次相遇时相遇节点就是环的入口。阶段二就是整道题的精髓。先看阶段一的 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的人很少。而后者往往就是面试官心里给你加分的关键。最后分享一个小技巧把环想象成操场跑道慢指针是散步的人快指针是跑步的人。第一次碰头只能证明你俩在同一片场地想找到“入口”得用路程差算出那个唯一的入场点。这个画面感建立起来之后这道题基本就长在你脑子里了。