环形链表 II 详解：从快慢指针到入环点的数学推导

我第一次做这道题不是在力扣提交页面而是在一次模拟面试的白板上。当时我已经写出了 141 题的快慢指针解法面试官点点头然后追问了一句如果链表有环你怎么返回入环的那个节点我一下愣住了。用哈希表当然能解但 142 这道题的名声就在于它要求 O(1) 空间。那一刻我才意识到环形链表这个系列真正难过的地方从来不是判断有没有环而是从有环推进到环在哪。如果你也卡在这一步这篇就当作一个踩坑复盘我们一点一点把这道题啃透。1. 题面拆解环形链表 II 到底难在哪1.1 题意与最朴素的解法题目本身不长一句话就能说完给定一个链表的头节点head返回链表开始入环的第一个节点如果链表无环则返回null。注意题目还附带一个要求——不要修改链表结构。最直白的解法是拿哈希表一路走一路记。每访问一个节点先看它是否已经在集合里出现过如果出现过那么它就是环的入口否则把它加进集合继续往下走。public ListNode detectCycle(ListNode head) { SetListNode visited new HashSet(); ListNode cur head; while (cur ! null) { if (visited.contains(cur)) { return cur; } visited.add(cur); cur cur.next; } return null; }这个思路直观到不能再直观我自己第一次做这道题时就是这么 AC 的。代码提交通过整个人挺高兴但冷静下来发现一个尴尬的事实这个解法的时间和空间复杂度都是 O(n)。在力扣的进阶要求面前哈希表解法只能算半个答案。1.2 为什么 141 到 142 的跳跃比想象中大141 题问的是链表中是否存在环。你只需要让快慢指针跑起来如果某一刻两个指针指向同一个节点就说明有环。141 的答案是布尔值true 或者 false代码写起来甚至比很多字符串题还短。但 142 不一样它要的不是有没有环而是环的入口节点在哪。从判断存在到精确定位难度上了一个台阶。很多人背过一个结论相遇之后把快指针挪回头节点两个指针每次都走一步第二次相遇的位置就是入口。这句话流传很广但如果你只是背下来面试官一句为什么两个指针第二次相遇一定在入口场面就会冷下来。我自己也经历过这个背得下来但解释不了的阶段。后来在 IDE 里反复画图、推导才真正搞明白这句话背后的数学关系。这也是我为什么坚持要写这篇的原因——网上的题解很多但多数只给结论不讲为什么。1.3 面试中的真实考察点这道题在面试中出现频率很高因为它不是单纯背模板就能糊弄过去的。它把好几层能力揉在了一起基础数据结构链表节点怎么遍历怎么判断next是否为空算法范式双指针思路尤其是快慢指针的运用数学建模把几何图形转化为变量和等式这是最核心的一层表达与推导能不能把相遇为什么要发生、入口为什么能定位讲清楚。面试官真正在意的不是你见过没有而是你能不能现场推出来。所以我强烈建议哪怕你已经背下了代码也要把第 3 节的推导完整走一遍。2. 快慢指针检测环龟兔赛跑背后的模数直觉2.1 为什么慢指针不会被快指针跳过很多初学者会有这个疑问快指针每次走两步慢指针每次走一步快指针会不会直接越过慢指针导致永远碰不到答案是不会。关键在于快指针相对慢指针的速度是 1 步——快指针走两步慢指针走一步每个时间单位内快指针比慢指针多走一步。如果它们都在环里快指针每一次相对靠近的程度就是 1不存在一次靠近 2 步的情况自然也不可能越过对方。你可以把环想象成一条圆形跑道快指针和慢指针是两辆速度不同的车。因为相对速度只有 1所以后车追上前车只是时间问题不会有嗖一下越过这种戏剧性场面。用钟表来类比更形象分针走得比时针快但它们的相对速度是固定的所以在 12 小时内会相遇很多次而不是分针一跳就跑到时针前面看不见了。2.2 环内相遇的必然性与最坏情况进一步追问快指针为什么一定能在慢指针走完一圈前追上它这里有个严格的说法。假设慢指针刚到达环入口的那一刻快指针已经在环内了我们把快指针在环内领先慢指针的距离记为 d且 0 d L其中 L 是环长。快指针每轮相对慢指针前进 1那么最多 L-1 轮就能追上。也就是说慢指针进入环后还没走出完整一圈就会被快指针追上。这个结论很重要因为后面的推导要假设慢指针在相遇前没有走满一圈。如果慢指针真的绕了好几圈才被追上那么慢指针的路程就不再是 ab而会变成 a b mL公式会复杂很多。幸运的是快指针的速度是慢指针的两倍这个两倍保证了相遇发生得足够早才让推导变得干净。2.3 写检测部分代码时的第一个坑判断环形链表的代码非常短但初学者提交时最容易撞上的坑是空指针异常。很多人会写成这样while (fast.next ! null fast.next.next ! null) { ... }这个写法在head为null或者链表只有一个节点时会直接抛NullPointerException。因为fast本身可能已经为null再去访问fast.next就崩了。稳妥的循环条件应该是while (fast ! null fast.next ! null) { slow slow.next; fast fast.next.next; }先保证fast非空再保证fast.next非空然后才能放心地执行fast.next.next。这个顺序看起来是小事但我在调试里见过不少因为这个崩溃的代码所以单独拎出来说一下。3. 入环点的数学推导相遇之后为什么还要再走一段3.1 三个距离的设定要理解入口定位先定义三个关键距离。建议你手边拿张草稿纸画一条带环的链表边看边读a链表头head到环入口节点的距离按边的数量计b从环入口出发沿着next方向走到快慢指针相遇点的距离c从相遇点继续沿next方向走回到环入口的距离。显然整个环长L b c。这个分解是整个推导的基础。画图的时候要注意快慢指针的相遇点并不一定在环入口的正对面。它只是一个满足特定等式的几何位置具体在哪取决于a和环长的关系。这也是为什么不能把相遇点直接当成入口。3.2 等式变形与关键结论忽略链表的入口和出口我们只看路程。慢指针从head出发到达相遇点时总路程是a b因为它在环内还没走满一整圈就被追上了。快指针从head出发到达同一个相遇点时总路程是a b kL其中k是快指针在环内比慢指针多走的圈数k 1。快指针速度快一倍所以相同时间内它走的路程是慢指针的两倍2(a b) a b kL两边同时减去a ba b kL进一步变形a kL - b (k - 1)L (L - b)由于L b c所以a (k - 1)L c这个等式是整道题的灵魂。它告诉我们从链表头到环入口的距离a等于从相遇点到环入口的距离c加上整数个环长。于是我们可以设计一个非常优雅的操作让一个指针从head出发另一个指针保持在相遇点两个指针都以步长 1 前进。当第一个指针走完a步到达环入口时第二个指针走的路程是a步也就是(k-1)圈再加c步同样恰好绕回到环入口。两者在入口处相遇。这就是第二次相遇即入口的真正来历。3.3 直觉理解用取模代替背公式公式背起来容易忘我后来给自己换了一种直觉理解想通之后就再也丢不掉了。快指针比慢指针多走的路程恰好是环长的整数倍。多走的那段路程数值上等于慢指针走过的路程也就是a b。这就意味着慢指针从相遇点再走a步会回到环入口。与此同时一个从head出发的指针走a步也会到达环入口。于是两个不同出发点、相同速度的指针在走完a步之后命运般地落在同一个点上。我的记忆锚点是这样一句话把相遇点当成一个临时起点把head到入口的距离当成一段固定的旅程那么相遇点到入口的距离在模环长的意义下恰好等于这段旅程。一旦建立了这样的图景代码里为什么要重置一个指针到头节点就变得顺理成章了。3.4 a0 的边界情况入口在头节点很多人推导完公式就觉得大功告成却忽略了一个特殊场景环入口恰好就是头节点也就是a 0。这种情况在题目里很常见比如head指向自己形成自环或者整个链表首尾相接形成一个不算入口偏移的大环。此时公式变成0 (k-1)L c当k 1时c 0。这意味着相遇点就是这个环入口两个指针第一次相遇的位置就在入口处。代码里为什么会体现这个边界因为当你重置一个指针为head后如果head恰好就是入口那么ptr slow从一开始就成立循环体不会执行直接返回ptr。这是正确的行为但如果你在写代码时没有意识到这一点可能会怀疑自己的判断甚至加一些多余的处理导致出错。所以遇到这种用例时要淡定程序是对的。4. 直接可抄的代码与边界条件排查4.1 Java 双指针完整实现把上面的推导翻译成代码就是下面这样。我用ptr作为从head出发的指针避免复用fast造成混淆可读性更好public class Solution { public ListNode detectCycle(ListNode head) { if (head 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) { // 第二阶段从头节点和相遇点同步走入口处相遇 ListNode ptr head; while (ptr ! slow) { ptr ptr.next; slow slow.next; } return ptr; } } return null; } }整段代码的骨架只有两个循环第一个循环负责检测环并找到第一次相遇点第二个循环负责从相遇点出发定位入口。很多人会把两个阶段混在一起写结果越改越乱。分开写思路清晰也不容易出错。4.2 边界条件一览表我在调试这道题时整理过一份边界条件表每次写完代码就照着过一遍基本能筛掉大部分隐性 bug场景链表结构期望结果代码行为空链表nullnull进入第一行判断直接 return null单节点无环1 - nullnullfast 为 null退出循环return null单节点自环1 - 1节点 1slow 和 fast 同时指向 1ptrhead 直接命中双节点无环1 - 2 - nullnullfast.next 为 null退出循环标准环1 - 2 - 3 - 4 - 2节点 2相遇后 ptr 走到节点 2slow 也绕回节点 2入口在头节点1 - 2 - 3 - 1节点 1a0ptrhead 直接返回这张表我在手写代码前都会在脑子里过一遍。写代码时养成的习惯是先把空指针、单节点、无环这三类最简单的场景跑通再去看复杂环。4.3 哈希表解法O(n) 空间换直观有时候面试官也会接受哈希表解法尤其是当你先讲清楚思路再补充一句如果要 O(1) 空间我会用快慢指针之后。哈希表版本的代码前面已经给过了它最大的优点是直观、不易出错、不需要任何数学推导。它的缺点是空间复杂度为 O(n)。在极端情况下比如链表有几十万个节点且环在很靠后的位置哈希表会占用大量内存。力扣的进阶要求其实也在暗示这道题最令人舒适的地方不是朴素解法能 AC而是你能不能用更优雅的方式解决问题。另外多说一句有人会想着每访问一个节点就把它的 next 改成某个特殊节点来打标记。这种思路可行但它修改了链表结构不符合题目要求面试时也别这么回答。5. 那些年踩过的坑错解、陷阱与调试经验5.1 网上流传的错解把相遇点当入口这道题在网上有一个流传度很广的误传快慢指针相遇的位置就是环的入口。这个说法是错的但因为它在一部分用例上恰好能通过导致很多人被误导。反例很容易构造。你画一个入口在位置 2、总节点数 4 的环形链表1 - 2 - 3 - 4 - 2。快指针和慢指针第一次相遇大概率在节点 4 附近离入口节点 2 还有一段距离。如果把相遇点直接返回必然报错。为什么这个错解还会流传因为当a 0且k 1时相遇点的确就是入口。有些刷题者只用了少量用例验证就以为自己发现了规律实际上只是巧合。这提醒我们验证算法时一定要覆盖多种结构不能只测 happy path。5.2 空指针与死循环while 条件怎么写才稳我在第 2 节提过循环条件的坑这里再展开说几个实操层面的细节。第一个坑fast.next.next。这个表达式要求fast和fast.next都不为 null。循环条件必须写while (fast ! null fast.next ! null)顺序还不能反。第二个坑在第二个循环里如果误把ptr初始化为head.next那么当入口就是head时会陷入无限循环。因为ptr永远在slow前面追不上或者两者交错。保险做法是ptr head。第三个坑有环时如果第二个循环的退出条件只写了while (ptr ! slow)而忘记移动其中一个指针就会死循环。两个指针必须同步移动。我在本地调试时习惯在循环内打印两行日志System.out.println(ptr ptr.val); System.out.println(slow slow.val);这样每次都能直观看到两个指针的逼近过程。如果日志一直不出现相等的情况那一定是循环逻辑写错了。5.3 为什么快指针不能随便改成 3 倍速这是一个超出主流题解范围的扩展问题但面试官偶尔会问而且真正理解的人不多。快指针如果改成每次走 3 步检测环本身仍然是可行的但有两个问题。第一个问题是相对速度变成了 2快指针在环内可能跳过慢指针。假设某一时刻慢指针在前两者距离为 1快指针一次走 3 步慢指针走 1 步相对距离瞬间变成 -1也就是快指针越过慢指针到了前面。因为快指针落点永远只在某个固定模数位置两者的相遇就不再是必然事件。第二个问题是即使发生了相遇入口的公式也不再是第 3 节推导出来的那个简洁形式。快指针速度改成 3 倍后路程等式会变成3(ab) abkL推出来的关系式不再等同于从 head 走 a 步等于从相遇点走 c 步加若干圈。所以2 倍速不是随便定的它同时兼顾了必然相遇和推导简洁两个条件。5.4 调试环形链表问题的实用技巧调试这类问题我有个固定的流程分享出来供你参考。第一步先写一个辅助函数用来快速构造带环链表。比如输入一个数组和一个入环位置下标就能生成对应的环形链表。这样本地跑测试用例时不用手动拼接节点省时省力。public static ListNode buildCycle(int[] values, int pos) { if (values.length 0) { return null; } ListNode dummy new ListNode(0); ListNode cur dummy; ListNode cycleEntry null; for (int i 0; i values.length; i) { cur.next new ListNode(values[i]); cur cur.next; if (i pos) { cycleEntry cur; } } if (cycleEntry ! null) { cur.next cycleEntry; } return dummy.next; }第二步先用哈希表解法跑一遍确认有环这个前提成立。如果哈希表能返回入口再跑双指针解法这样可以把问题定位在检测逻辑错还是入口定位错。第三步用 4.2 的边界表逐条验证。尤其是自环和入口在头节点这两种情况很容易出问题。这套流程帮我省下了大量调试时间。你在刷题时也可以试试特别是面对链表类题目一个合适的辅助函数能省很多事。6. 从力扣到实际工程环形结构还能怎么用6.1 287题寻找重复数一个让人拍案叫绝的转化刷完 142 之后这道题就变成了一道送分题。题目是这样的一个包含n 1个整数的数组nums每个整数都在[1, n]范围内所以至少存在一个重复的数。要求你找出这个重复的数并且不能修改数组只能用 O(1) 的额外空间。这题最漂亮的解法就是把数组想象成链表。索引i的下一个节点是nums[i]也就是i - nums[i]。因为所有nums[i]都在[1, n]范围内所以从索引 0 出发这条链表必然进入一个环而环的入口就是那个重复的数。public int findDuplicate(int[] nums) { int slow 0; int fast 0; // 第一阶段在环内相遇 do { slow nums[slow]; fast nums[nums[fast]]; } while (slow ! fast); // 第二阶段找到环入口 int ptr 0; while (ptr ! slow) { ptr nums[ptr]; slow nums[slow]; } return ptr; }我第一次看到这个转化时心里是服气的。它把一个数组问题映射成链表问题再套用 142 题的完整思路全程不需要统计频率不需要排序不需要额外空间。这就是快慢指针方法论的高光时刻。6.2 快慢指针的其他应用场景快慢指针在链表题里是一整个家族不止 142 这一道。我把它涉及的常见场景列一下方便你举一反三环形链表只判断是否有环快慢指针相遇即 true链表的中间结点慢指针走一步快指针走两步快指针到末尾时慢指针正好在中点链表中倒数第 k 个节点快指针先走 k 步然后快慢指针同步走快指针到末尾时慢指针就是倒数第 k 个节点回文链表先用快慢指针找到中点反转后半段再逐一比较。这些题的核心都是同一个思想利用速度差制造相对位移从而在单次遍历中完成某些查找或判断。掌握了 142 的推导再去看这些题会轻松很多。6.3 环形链表在真实系统里的身影很多人刷题时会问这东西除了面试到底有没有用环形链表的思想在真实系统里其实无处不在只是不会直接写成ListNode而已。操作系统里的时间片轮转调度就是用一个循环队列本质是环让进程轮流使用 CPU。生产者消费者模型里的环形缓冲区也是环状结构用来在固定大小的内存区域里高效读写数据。垃圾回收算法在检测循环引用时要判断对象引用图里是否存在环思路和链表判环同源。文件系统里如果出现目录软链形成的循环引用也需要类似的手段去发现和打破环。这些场景里检测环和定位进入点的思想会以各种形式反复出现。142 这道题的价值不只是让你会写一个双指针函数更是帮你建立一种识别环状结构的直觉。有了这种直觉以后遇到类似问题你会下意识地往快慢指针方向想。最后分享一个我自己的土办法。学这道题时我反复在本地用buildCycle构造各种奇形怪状的环然后在关键位置打印日志看slow和fast每一步落在哪个节点。跑了两三个用例之后那个抽象的a、b、c关系就在脑子里扎了根。刷题这事光看别人的推导永远差一层自己动手画一遍、推一遍、在 IDE 里看一遍才算是真正把它吞进去了。这题刷透之后快慢指针这一整个分支基本就打通了后面再去碰 141、876、287 都会顺畅得多。