快慢指针破解环形链表：判定与入环点查找全解析

刷题进入到第四天总算遇到了链表里一个让我觉得“有点意思”的题目。前面几天还在跟数组、滑动窗口较劲突然转到链表一开始还挺不适应的尤其是单链表那种“只能往前不能回头”的遍历方式很多数组里理所当然的操作到了链表里都会变得别扭。直到碰见环形链表配合着快慢指针的解法才有一种“原来还能这么玩”的开窍感。这篇就专门聊聊快慢指针这个思路以及它怎么直接解决环形链表的判定和入环点查找问题。代码我会给Java版本但思路完全通用C、Python、Go照着改改就成。不管你是准备面试、刷题还是单纯在学校上数据结构课觉得链表那章昏昏欲睡这篇文章都值得你认真看一下。我会把为什么能这样做的底层道理讲明白而不是让你背模板。1. 为什么快慢指针能检测环形链表——核心思路拆解1.1 先把“快慢指针”这个东西说清楚快慢指针英文里有个特别形象的说法叫“龟兔赛跑”在链表相关的题里非常常见。核心操作极其简单定义两个指针都从链表头出发慢指针每次往后走一个节点快指针每次往后走两个节点。如果你心里想的只有代码实现那确实就是这么点事。但关键问题是为什么一个走两步、一个走一步就能判断链表里有没有环如果链表没有环那快指针会最先碰到null任务直接结束说明这个链表是个普通的单向链表。如果链表里有环那快指针和慢指针迟早会再次相遇——注意这里说的是“再次”因为它们在起点也算是相遇过一次。这两个指针一旦进入环里就好比两个人在一个圆形操场上跑步一个速度快、一个速度慢快的那个人迟早会从后面追上来套圈撞到慢的那个人。这个“追及”过程就是快慢指针检测环的核心依据。1.2 一个生活化类比操场套圈我试着把这个过程讲得更直观一点。假设你和朋友在一个环形跑道上锻炼你走两步他走一步而且两人同时出发。因为他比你快所以他会慢慢地拉大与你之间的距离。但是跑道是圆的他不可能是无限远离你当他跑完一整圈之后自然就会从你身后追上来。链表里的“环”就是这个操场。慢指针每走一步快指针走两步相对速度是“一步”。一个关键的事实是只要环存在快指针相对于慢指针的靠近速度是“每轮靠近一个节点”那么它一定会追赶到慢指针哪怕这个环里只有一个节点——如果环里只有那个节点快指针走两步慢指针走一步两人都会反复回到那个节点上这不叫相遇这也太刻意了实际上环长至少为1的情况下快指针第二次到达这个节点时慢指针刚好第一次到达之后快慢指针同步相遇就是必然。这里面有个隐藏前提快慢指针都进入了环里之后才谈得上追及。如果环很长而链表头到环入口的距离也很长那在慢指针进环之前快指针可能已经在环里绕了好几圈了。但这没关系快慢指针相对速度固定只要慢指针进入环接下来的事就是时间问题。1.3 环形链表检测的两个核心事实我们先理清两个关键结论后面的代码、推导都会用到第一如果链表无环快指针会先走到链表末尾的空指针这个可以当作终止条件。第二如果链表有环则快慢指针一定会在环内的某个位置相遇。为什么一定会相遇因为快指针每次比慢指针多走一步相对于慢指针而言“距离”在逐渐缩短。慢指针在环内绕圈快指针也在绕圈只要时间足够快指针一定追得上。听到这里可能有人会想快指针速度是慢的两倍会不会出现“刚好跳过”的情况比如慢指针在节点A快指针在相邻的节点B然后一下走到节点C恰好错过了这个疑虑我以前也有后来专门画图推导过。答案是不会。因为快指针相对于慢指针的速度是一步一个节点。当快指针距离慢指针还差一个节点时下一轮操作之后慢指针前进一格快指针前进两格结果就是快指针到达慢指针原来的位置而慢指针已经走到下一格两个人刚好相邻——以此类推在节点层面上它们会“擦肩而过”再“追上”但不可能是“瞬间穿过”。详细证明只要考虑相对运动即可追赶速度1节点/轮只要环有限迟早追上。而且由于每次移动的步长是整数相对距离每轮严格减少1不存在跳过的情况。所以在代码里你不需要额外记录环内哪个位置是特殊点你只需要在快慢指针相遇时停一下然后利用这个相遇点做后续计算。2. 环形链表的判定与入环点查找——两道经典题一次吃透2.1 环形链表基础版判断有没有环这道题对应力扣141题。需求就是给你一个链表的头节点让你判断链表中有没有环。如果只是判断是否存在环代码其实非常短public boolean hasCycle(ListNode head) { if (head null || head.next null) { return false; } ListNode slow head; ListNode fast head.next; while (slow ! fast) { if (fast null || fast.next null) { return false; } slow slow.next; fast fast.next.next; } return true; }这里有个细节值得专门说一下很多教材里的写法是让快慢指针都从head出发循环条件是fast ! null fast.next ! null然后每次移动。但我个人倾向于把快指针先往前挪一个位置fast head.next这样做的目的是让两个指针不要一开始就相等否则while循环会进不去。如果你想让快慢指针严格从同一个起点出发写成下面这种形式也可以public boolean hasCycle(ListNode head) { ListNode slow head; ListNode fast head; while (fast ! null fast.next ! null) { slow slow.next; fast fast.next.next; if (slow fast) { return true; } } return false; }第二种写法更常见因为它在快慢指针相遇的瞬间才判定有环逻辑清晰。两种写法都能用看个人习惯。我建议刷题的时候固定一种写法形成肌肉记忆面试的时候不容易写错。2.2 环形链表进阶版找出入环点判断完有没有环紧接着就会有一个更难的问题如果链表有环环的入口节点是哪一个这道题对应力扣142题。你不仅要证明有环还要精确指出从链表头出发走多少个节点就进入环。这题的代码实现也不复杂但难就难在为什么可以这样做。先说结论先用快慢指针找到相遇点然后让一个指针从链表头重新出发另一个指针从相遇点继续出发两个指针都改为每次走一步它们再次相遇的那个节点就是环入口。public ListNode detectCycle(ListNode head) { 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; } // 第二阶段找入环点 ListNode ptr head; while (ptr ! slow) { ptr ptr.next; slow slow.next; } return ptr; }这个解法很简洁但要是说不出背后的数学道理面试官追问两句就会露馅。所以接下来我重点推导一下。2.3 关键数学推导为什么相遇点能帮你找到入环点我们给链表里几个关键位置取名字。链表头到入环点之间的距离设为a。入环点出发沿着链表方向走到快慢指针第一次相遇的那个节点这段距离设为b。从相遇点继续走回到入环点这段距离设为c。环的周长是b c。当快慢指针相遇时慢指针总共走过的距离是a b。那快指针呢快指针速度是慢指针的两倍所以相同时间内快指针走过的距离是2 * (a b)。但快指针不是一条直线走到相遇点的它在进环之后可能已经绕了若干圈。假设它绕了n圈n是正整数且至少为1那么快指针的总距离还可以写成a n * (b c) b。把两个表达式联立起来看2 * (a b) a n * (b c) b整理一下a b n * (b c)也就是a n * (b c) - b n * (b c) - (b c) c (n - 1) * (b c) c这个式子告诉我们一件重要的事从头节点到入环点的距离a等于从相遇点出发绕了(n - 1)圈之后再走一个c的距离。而c恰恰就是相遇点回到入环点的那段距离。因此如果一个指针ptr从链表头出发另一个指针slow从相遇点出发两者都一次走一步那么ptr走到入环点的时候slow也刚好绕完了(n-1)圈回到入环点。两个指针自然就相遇在入环点上。这里特别解释一下免得有人绕晕如果n1式子简化为ac意思是头节点到入环点的距离等于相遇点到入环点的距离两个指针从两个位置同时出发步长一样肯定在入环点碰头。如果n1相当于慢指针多绕了几圈但因为时间同步绕圈的部分会相互抵消最终还是会同时出现在入环点。理解了推导过程这题就不再是背代码而是真的会了。3. 代码实现细节与常见写法对比——让代码真正能跑通3.1 为什么循环条件必须写fast ! null fast.next ! null写链表题的时候最痛苦的事情就是空指针异常。快慢指针里的循环条件尤其讲究。先想一个问题快指针每次走两步它在循环体内部会执行fast.next.next。如果fast.next已经为null再取fast.next.next就直接抛异常了。所以循环条件里必须保证两件事第一fast ! null保证取fast.next不越界。第二fast.next ! null保证取fast.next.next不越界。只要这两个条件任意一个不满足说明链表已经走到头了不可能有环。我见过不少人把循环条件写成while (slow ! fast)然后走进循环体再判断快指针是否为空。这样写不是不行但逻辑顺序一定要对先判空再移动指针。对于141题的第一种写法我给出了先判空再移动的版本那也是常见的。3.2 哈希表方案与快慢指针方案对比其实检测环形链表还有一种“暴力但直观”的解法用哈希集合记录访问过的节点。每遍历一个节点先看它是否已经在集合里如果在说明成环如果不在就加进去然后继续往后走。代码也很简单public boolean hasCycle(ListNode head) { SetListNode seen new HashSet(); ListNode cur head; while (cur ! null) { if (seen.contains(cur)) { return true; } seen.add(cur); cur cur.next; } return false; }但这方案有两个明显问题一是空间复杂度是O(n)因为你要额外存储整个链表里出现过的所有节点引用。如果链表足够长内存消耗会很夸张。二是它没有快慢指针那种“优雅感”。面试的时候如果你能用快慢指针做出来通常会被认为对问题有更深刻的理解。快慢指针的空间复杂度是O(1)而且还能直接用于寻找入环点。所以面试里想稳的话优先快慢指针。3.3 一个有价值的追问快指针一定要走两步吗有的读者可能会好奇快指针每次走两步是基于什么确定的走三步行不行先说结论快指针每次走两步是理论最优因为这样相对速度是1节点/轮能保证在有限环内必定相遇。如果你让快指针每次走三步那么快指针相对慢指针的速度是2节点/轮有可能出现“跳过”相遇点的风险。举一个极端但实际可能出现的例子环长为bc2快指针和慢指针都在环内且快指针在慢指针前方正好两个节点。快指针一次走三步有可能一步迈过慢指针然后两个人永远卡在某种错开的状态里。所以“快指针每次比慢指针多走一步”才是最安全的配置。这也是为什么面试题的标准解里几乎都是快指针两步、慢指针一步不要自己随意改成三步、四步。3.4 两个题目的代码对比速查表对比维度141 环形链表142 环形链表II核心需求只判断链表是否有环不仅要判断还要返回入环点返回值booleanListNode无环则null阶段数一个阶段两个阶段找相遇点 找入环点空间复杂度O(1)O(1)时间复杂度O(n)O(n)关键中断条件快指针走完即可判定无环先判定无环再用相遇点推导时间复杂度的O(n)要注意即便快指针可能绕了好几圈但因为慢指针最多走完整个链表的节点数加一圈环整体上还是线性级别。不用太纠结快指针“多跑了几圈”的事情它在环形里跑的圈数是有限的和时间复杂度不冲突。4. 刷题第四天的实战记录与踩坑经验——我的经验供你参考4.1 我在调试中踩过的三个典型坑第一个坑没有处理空链表和单节点链表。head null || head.next null这种边界条件我一开始经常漏掉。虽然代码在LeetCode上有可能侥幸过但真实面试的时候边界条件也是评分点尤其是面试官盯着你的空指针处理时。养成习惯链表题先检查头节点和头节点的next是否为空。第二个坑快慢指针都从head出发时循环条件写错导致死循环。我第一次写142题时直接把141的代码复制过来改结果while (fast ! null fast.next ! null)的判断和if (slow fast)的位置放错了导致两个指针一开始就相等然后走进死循环。这里要记住一个细节如果你用141题“先移动后判断”的写法那么循环条件就是要保证能进入下一步如果用142题那种“先找相遇点再break”的写法要先让快慢指针移动再判断是否相等。第三个坑误入“环入口等于链表头”的陷阱。如果链表头本身就在环上detectCycle返回的应该是头节点本身。有人会用ptr head.next来找入口结果把第一个节点跳过去了。142题第二步里ptr应该直接从head出发不要自作聪明地提前走一步。4.2 常见错误速查表错误现象可能原因解决办法运行时报空指针异常用fast.next.next时没有预先判断fast.next是否为null循环条件加上fast ! null fast.next ! null函数返回null但实际有环快慢指针可能在入环前就退出循环检查循环条件是否提前终止head.next边界是否处理正确死循环快慢指针从head出发后循环体内未先移动就直接判断相等判断顺序调整为“先移动后判断”入环点返回错误节点第二步ptr起点不对或两个指针步长不一致确保从head出发的指针和从相遇点出发的指针都是每次走一步环入口计算有偏差没有正确理解a(n-1)*环长c的推导建议手动画一个a2, b2, c1, 环长3的例子验算一遍画图验证这一步真的很推荐。以前我总觉得数学推导看看就懂了后来发现只有当自己亲手画出一个具体实例把每一步指针的移动都标出来才算真正掌握了。你可以随便设一组简单的值比如链表头到入环点是2个节点环的长度是3个节点入环点到相遇点是2个节点然后模拟指针一步一步移动看看到底为什么会同时到达入环点。整个过程跑下来这个推导就长在你脑子里了。4.3 快慢指针不只用于环形链表第四天刷完环形链表之后我发现快慢指针这个思想其实还能用在一堆看似不相关的题上。最常见的例子是找链表的中点。让慢指针每次走一步快指针每次走两步当快指针走到链表末尾时慢指针正好走到中间位置。这比先遍历一遍算长度、再走一半的做法要省一次遍历。还有一个经常用的场景找链表倒数第k个节点。这种题可以用“双指针法”但不太一样——先让一个指针走k步然后两个指针同步走当先走的那个指针到底时后走的那个正好停在倒数第k个位置。这个思路本质上还是“制造一个固定距离差”。另外快慢指针配合“反转链表”还能解决回文链表的判断问题。先用快慢指针找到中点再反转后半段然后逐节点比较前半段和反转后的后半段是否相等。这个思路可以把空间复杂度压到O(1)。甚至在一些数组问题里也有快慢指针的影子比如“原地去重”这种经典题本质上是一个指针负责探路另一个指针负责记录最终有效位置。这也是“快慢指针”思想的一种变体。4.4 一个更深入的问题环的起点为什么不能用“第一个重复出现”来判断有很多人一开始会想既然有环那顺着链表遍历下去肯定会重复经过某个节点。那我能不能用哈希表记录所有节点第一次遇到重复节点时就认为它是入环点这个做法不能保证正确原因很简单重复出现的节点一定是入环点吗不一定。入环点是环的入口但重复出现的那个节点可能是环里的任意一个节点。因为一旦进入环所有环内节点都会无限重复你只能检测到“某个节点出现了第二次”却无法确定这个节点是不是“第一个进入环的节点”。除非你把链表从头到尾的路径完整记录下来才能判断谁是最早的重复节点。而这种方法本质上就是哈希表方案空间复杂度是O(n)。快慢指针的高明之处在于它不靠“记录历史”而是靠位置关系的数学推导直接锁定入环点。4.5 我现在的做题习惯第四天过后我渐渐摸索出一套比较顺的做题流程写在这里给大家参考拿到一个链表题先别急着写代码。第一个步骤永远是画图。我一般只会画最简结构几个方框加几个箭头把指针的运动轨迹模拟一遍。第二个步骤是把题目要求的“终止条件”想清楚——这道题里链表是空的时候怎么办只有一个节点的时候怎么办遍历到null算不算结束。第三个步骤才是动手写代码。写完代码之后我还会再画一次图去“跑”代码特别是有环的情况模拟几次移动确保指针没有越界。第四天这道题让我意识到刷题并不只是背题而是要在脑子里建立一种“动态图景”你能想象指针在链表中移动的画面你才能判断一个解法是对是错。快慢指针尤其适合这样学因为它的每一步移动都很具体有没有环、走到哪里了都清清楚楚。如果你也正处在刷题初期遇到链表题总觉得抽象我建议你拿一支笔和一张草稿纸把链表的每个节点画成小方块把每个指针画成一个小三角。快慢指针谁在前、谁在后慢慢走几轮很多东西就自然通了。这道环形链表题就是那个让你从“背模板”转向“真正理解”的转折点。