力扣第142题环形链表 II是我刷链表专题时印象最深的一道题。第一问判断链表是否有环很多人一口气就能写完但第二问找出环的入口却让不少人在推导上卡了很久。我第一次做这道题的时候也是把代码背下来了但没有真正理解为什么第二次相遇的位置就是入口后来花了大力气把数学关系捋清楚才发现这道题的精髓根本不在那十几行代码而在相遇点和入口之间那个不起眼的等式。这篇文章不打算只贴一份答案。我会把快慢指针为什么能解决这个问题、相遇点怎么算出入口、代码里哪些细节容易踩坑、面试时怎么把推导讲清楚全部拆开说一遍。不管你是在准备面试还是单纯想把链表这类题吃透这题都值得花半小时弄明白。我先说结论这题的最优解依赖一个简单但非常巧妙的数学关系理解了它你甚至不用背代码。1. 这道题到底在问什么1.1 从判环到找环入口题面很短给定一个链表的头节点如果链表中有环返回环的入口节点如果没有环返回null。也就是说它比判断是否有环多了一步不仅要告诉你有环还要把那个环开始的位置指出来。很多人会把两问合并起来看觉得只要在判环代码里加几行就能搞定。但真正动手写的时候会发现如果不理解相遇点和入口之间的数学关系写出来的代码很可能只是在碰运气。我见过不少同学第一版用HashSet记录节点代码是能跑但面试官一问能不能不用额外空间就卡住。这道题默认的进阶要求就是O(1)空间这也是为什么快慢指针方案绕不开。1.2 快慢指针为什么是标准解快慢指针的核心玩法一个指针每次走一步另一个指针每次走两步同时从head出发。如果链表没有环快指针会先到尾部循环正常结束如果链表有环两个指针一定会在环内某个位置相遇。这里有个很自然的疑问为什么快指针走两步不能走三步四步原因很简单走两步时快指针相对慢指针的速度是一步两个指针之间的距离在每个时间单位内只减少1快指针不会跳过慢指针。走三步的话相对速度是两步如果两个指针之间只差一个节点快指针这一步就可能直接从慢指针头顶跨过去本来应该相遇却错过了。虽然多绕几圈后理论上有可能会撞上但分析和证明都会复杂很多完全没有必要。用一个跑道例子来理解特别直观两个人绕圆形操场跑步跑得快的人速度是另一个人的两倍那么跑得快的人一定会在某一圈追上跑得慢的人。链表里的环就是操场快指针就是那个跑得快的人。1.3 脑中的第一个方案HashSet为什么不是终点先别急着否定HashSet。它的思路非常简单遍历链表把每个节点放进集合如果遇到某个节点已经在集合里那这个节点就是入口。这个解法完全正确时间复杂度O(n)写起来也很短十几行搞定。问题出在空间。HashSet在最坏情况下要存所有链表节点空间复杂度O(n)。如果链表很长比如几十万个节点这个集合会占用不少内存。题目虽然没有明确禁止HashSet但面试官大概率会追问一句能不能不用额外空间。所以HashSet可以作为第一版答案展示你的基础思路但最终要落到快慢指针这个O(1)空间方案上。2. 核心数学推导相遇点与入口的关系2.1 三个距离的变量定义要讲清楚从相遇点到入口那一步为什么可行必须做一点简单的数学。先定义三个距离从头节点到环入口的距离为a从环入口到第一次相遇点的距离为b从相遇点继续往前走回到环入口的距离为c环的周长为L显然L b c。注意这里的距离是沿着链表next方向走的步数不是几何距离。画图的时候把链表画成一条直线加一个圆圈入口在直线和圆圈的交接处。这个图很关键面试时最好直接在白板上画出来。2.2 方程推导与核心结论两个指针都从head出发慢指针走到相遇点因为它在进环之前走的是直线段进环后又走了一段b所以它一共走了a b步。快指针呢它在进入环之后可能已经绕了好几圈。设它比慢指针多绕了k圈k为正整数那快指针走的总路程就是a b kL。因为快指针速度是慢指针的两倍所以在同一段时间内快指针走的路程也是慢指针的两倍于是有2(a b) a b kL移项得到a b kL再进一步变形a kL - b (k - 1)L (L - b) (k - 1)L c这个式子说明什么说明从头节点走到环入口的距离a等于从相遇点走到环入口的距离c再加上若干个整圈。也就是说如果现在让一个指针从头节点出发另一个指针从相遇点出发两者都一次走一步那么它们走过a步之后会同时到达环入口。那个从相遇点出发的指针中途多绕了几圈但整圈对最终位置没有影响忽略掉之后它此刻正好站在入口。2.3 用一个具体例子验证光看公式可能还是有点抽象我举一个具体例子。假设a2b3环周长L5那么cL-b2。慢指针从head出发走到相遇点一共走ab5步快指针在同一时间走了10步正好等于ab1×L也就是k1。现在让一个指针从head出发另一个从相遇点出发都一次走一步。第一个指针走2步到达入口第二个指针从相遇点走2步c也正好是2所以它同样到达入口。两个指针在这里碰头。再举一个k2的例子a7b3L5c2。慢指针走10步到相遇点快指针走20步等于ab2L。从头出发的指针走7步到入口从相遇点出发的指针走7步等于绕了一圈再加2步同样停在入口。你看不管快指针在环里多绕了几圈第二次相遇点都锁死在入口。3. 代码实现与关键细节3.1 Python实现逐行拆解下面这份代码是我在实际刷题时整理出来的版本可以直接跑def detectCycle(head): 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 if not fast or not fast.next: return None ptr head while ptr ! slow: ptr ptr.next slow slow.next return ptr第一个while循环是标准的快慢指针判环。每次slow走一步fast走两步如果两指针相遇break跳出。这里要注意跳出循环有两种可能一是真的因为有环而相遇二是快指针已经走到链表末尾。所以循环结束后要做一个判断如果fast是null或者fast.next是null说明链表无环直接返回null。第二个循环是找入口的关键。我把一个新指针ptr放回headslow继续留在相遇点。两个指针都一次走一步直到它们相遇。根据前面的推导它们相遇的位置就是环入口。返回ptr即可。3.2 C和Java的快速对照如果你平时写C核心逻辑完全一样只是指针操作看起来更裸一点ListNode *detectCycle(ListNode *head) { if (!head || !head-next) return nullptr; ListNode *slow head, *fast head; while (fast fast-next) { slow slow-next; fast fast-next-next; if (slow fast) break; } if (!fast || !fast-next) return nullptr; ListNode *ptr head; while (ptr ! slow) { ptr ptr-next; slow slow-next; } return ptr; }Java版本也几乎一一对应只是判断写得更啰嗦一些。其实这个题的代码结构就那么几行真正的难点在于推导语言差异反而不重要。我建议你至少手写一遍自己熟悉的语言版本然后对着注释解释每一行在干什么。3.3 边界条件与空指针防线链表题最容易翻车的就是空指针。这道题的边界条件我整理过一遍基本就这几个case空链表head为null直接返回null不需要判断。单节点链表只有一个节点且next指向null没有环返回null。但如果不判断head.next后面fast.next.next会直接抛空指针。两个节点成环比如head指向node1node1指向head这种情况也算环。快指针第一次移动就会绕回来代码能正确处理。链表很长但环很小比如一万个节点环只有三个节点快指针会在环里绕很多圈这种case是检验实现是否健壮的好例子。while fast and fast.next这个条件写全基本能挡住大部分越界问题。但要注意第一次循环结束后的判断if not fast or not fast.next这个顺序不能反否则可能对None取next。3.4 复杂度为什么是O(n)和O(1)先说时间。慢指针从头走到第一次相遇点最多走链表节点总数加环内一圈级别的步数不会超过线性量级。更严谨地说慢指针进环前走了a步进环后又走了b步整体是ab而ab最大也就是链表长度加环长度依然是O(n)。快指针虽然走得多但它走的路程始终是慢指针的两倍所以整体复杂度依然是O(n)。空间复杂度是O(1)没有开HashSet没有递归调用只用了几个指针变量。这就是这版解法最大的优势也是面试官最想听到的答案。4. 实战中的常见问题与排查实录4.1 快指针步长为什么必须是2这个问题基本每个刷题的人都会问一次。从实现角度快指针走三步也能写出能跑的代码甚至某些数据下也能通过测试。问题在于一定会相遇这个结论不再显然成立。简单模拟一个场景环的长度是4快指针相对慢指针每轮前进2步。两个指针的位置可能会出现周期性错位本来该碰上的时刻却正好错过。虽然绕很多圈后可能还是会遇到一次但这已经不是一个稳定的判环方案。面试官要的是清晰可靠的逻辑所以标准答案就认准快走两步慢走一步不要想着炫技。4.2 第二次循环到底该用哪个指针有些实现会在第二个循环里写while ptr ! fast然后返回ptr。看起来也能跑因为fast此时还停留在相遇点。但这里有一个隐蔽的坑如果代码后面有人改动fast可能被复用就会出问题。稳妥的做法是固定用slow表示相遇点ptr从头走逻辑上更干净。我自己第一次写这道题的时候就是写成了while ptr ! fast最终通过测试了但看代码总觉得别扭。后来统一改成while ptr ! slow一眼就能看出含义ptr从头走slow从相遇点走两者再入口碰头。4.3 如何设计测试用例验证正确性光在力扣上通过还不够我建议自己额外构造几个case验证。比如无环链表1-2-3-null返回null。整个链表成环1-2-3-1入口是节点1。环在中间1-2-3-4-5-3入口是节点3。入口就是头节点1-2-1入口是节点1。很长的主链加很小的环100个节点后进入一个3节点的环。构造这些case时关键是手动设置next指针。比如1-2-3-4-5-3需要先建5个节点再让node5.next指向node3。写个辅助函数把这些case逐一跑过比直接提交到平台更有把握。4.4 面试表达顺序与常见追问我面试时有一次讲这道题因为紧张一上来就抛公式面试官皱了皱眉我立刻意识到没有铺垫。后来整理出一个更好的顺序先画链表图标出a、b、c三个距离然后说第一次相遇时慢指针走了ab快指针走了abkL又因为速度是两倍所以abkL于是a(k-1)Lc这就说明从head出发和从相遇点出发同时走会在入口相遇。这个顺序的关键在于先让对方看到图再用公式收尾。面试官通常还会追问几个问题为什么第二个循环里两个指针速度一样因为推导的前提就是两个指针同速一个从头走一个从相遇点走。如果链表没有环第二个循环会怎样根本不会进入因为第一个循环结束后已经判断了fast是否为空。快指针走三步行不行把不行的原因讲清楚就说明你真的理解了。5. 从这道题延伸出去5.1 环的长度怎么求如果题目进一步要求计算环的长度做法是在第一次相遇后让其中一个指针停在原地另一个指针一次走一步绕一圈回到原地计数就是环长。实现上第一次相遇后保持slow不动fast每次走一步当fast回到slow时步数就是环长。这里注意快指针不再走两步而是改成走一步避免跳过相遇点。这其实也验证了前面说的指针速度差为1才不会错过目标节点。一个问题搞懂之后变体题都会顺手很多。5.2 快慢指针是链表双指针家族的一员这道题属于更大的双指针技术家族。链表里很多问题都能用双指针解决判断是否有环、找环入口、找中点、删除倒数第N个节点。它们的核心思想都是利用指针速度差或位置差来定位。找中点那道题快指针走两步慢指针走一步快指针到底的时候慢指针正好在中点。它和判环的区别在于判环关注的是是否相遇找中点关注的是是否到底。一个是环一个是线性但代码结构高度相似。刷题阶段如果把这道题吃透后面做类似题会省很多力。5.3 相交链表解法里的同一个数学内核两个链表是否相交也有一个双指针解法两个指针分别从两个链表头出发走完自己的链表后切换到对方的链表最终会在相交点相遇如果没有相交则同时到达null。这个方案的数学依据和本题非常像都是路程差 相遇位置的思路。如果把两个链表看成在相交点合并成一个长链那么两个指针走过的路程最终会拉平差的正好是相交点前的长度差。你会发现环形链表II不是一个孤立的题它背后是处理带环结构的一套思维模型。5.4 后续还可以怎么扩展这道题的推导方式还可以迁移到很多场景。比如处理循环数组、判断图结构中的环、计算循环队列的起始位置等。核心都是同一件事利用速度差为1的追赶模型把一个看似不确定的环形问题转换成两个指针的相遇问题。如果你在刷题群里遇到有人问为什么二次相遇就是入口你可以直接用a、b、c三个距离给他讲一遍。能把别人讲明白才是真正掌握了。写到这里我最想提醒的是这道题的代码本身只有十几行但花半个小时把推导过程彻底啃下来比默写十遍代码有价值得多。刷题最大的误区就是背答案背完就忘换个问法就懵。如果你现在正卡在这道题上别急着看下一题先拿纸笔把公式推一遍再合上代码重新写三遍之后你想忘都难。