搞过链表算法的人一定绕不开“快慢指针找环”这个经典题。我第一次理解“重置快/慢指针”这套操作时确实觉得它有点魔法两个指针明明已经在环里相遇了把其中一个放回链表头部然后都改成一步一步走再相遇的位置居然就是环入口。后来我花了不少时间把背后的数学推清楚才意识到这套操作不是什么奇技淫巧它背后是明确的路程关系和几何含义。这篇文章就把这套逻辑彻底拆开。从“快慢指针为什么能相遇”讲起把重置指针那一步的数学证明展开给你看再辨析哪些场景适合用找环思路、哪些问题只是看着像但完全不是一回事。不管你是刚接触链表的初学者还是准备面试想补深度的开发者这篇应该都能帮你把“会背代码”变成“真正懂原理”。1. 快慢指针为什么能相遇从“相对速度差”理解找环1.1 链表环问题的基础模型先把问题限定清楚。单向链表中每个节点只有一个next指针所谓“有环”就是某个节点的next指向了链表中更早出现的节点于是沿着next一直走就永远走不到尽头。经典的判环题目要求只返回是否存在环进阶一点要求返回环的入口节点。快慢指针的玩法就是让两个指针从头节点出发慢指针每次移动一步快指针每次移动两步。如果链表无环快指针会提前走到尾部指向空循环自然结束如果链表有环两个指针最终会在环内某个节点相遇。这个思路的朴素类比就是两个人在环形跑道上跑步速度快的人经过足够长的时间一定会追上速度慢的人。放到链表里因为环是封闭的快指针一旦进入环早晚会从后面赶上慢指针。这里有个很多人没细想的前提为什么是快指针走两步、慢指针走一步而不是一个走三步一个走一步这需要从相对速度的角度去解释而不是简单背结论。1.2 为什么快指针恰好要走两步先设环的长度为 L。当慢指针刚进入环的时候快指针可能已经处在环内某个位置上。如果把“快指针距离慢指针还差多少步追上”记作 d那么 d 的取值范围是 1 到 L-1。之后每一轮循环快指针相对慢指针前进2 - 1 1步。也就是说两个指针之间的距离每轮稳定缩小 1最多经历 L-1 轮距离必然变成 0也就是追上。如果换成快指针每次走三步、慢指针走一步相对速度就变成 2。每一轮距离缩小 2看起来更快但这里存在一个隐患在环形轨迹上距离是模 L 计算的缩小 2 可能直接“跳过”相遇点。举个反例假设 L6某一时刻快指针落后慢指针 3 步那么距离变化序列是 3、1、5、3、1、5……永远到不了 0。换句话说快指针走三步慢指针走一步在某些环长和初始距离下理论上永远追不上。所以“快两步慢一步”不是拍脑袋定的它保证相对速度为 1使得“追上”这件事必然发生而且不会跳过。这是快慢指针找环算法的根基后面所有重置逻辑都建立在这个前提上。1.3 相遇点的本质一段可以“翻译”成等式的位置第一次相遇之后慢指针并没有走完整个环它可能只走了环长的一部分。这个相遇点本身没有特殊的“魔力”它只是恰好满足了某个路程数量关系。理解这个关系是理解重置操作的关键。假设链表头节点到环入口的距离为 a环入口沿着next方向到第一次相遇点的距离为 b相遇点继续沿着next方向走回环入口的距离为 c。那么环长 L b c。第一次相遇时慢指针走过的总路程 s a b因为慢指针进入环之后从环入口走到相遇点走了 b。快指针走过的总路程 f a b nL其中 n 是快指针在环内比慢指针多绕的圈数n 至少为 1。由于快指针速度是慢指针的两倍存在等式 f 2s。代入之后会得到一个非常漂亮的式子这个式子就是下一节推导的核心。2. 重置快/慢指针的数学推导环入口不是猜出来的2.1 相遇时的路程方程组把上一节的路程关系写成方程组慢指针s a b快指针f a b nL速度关系f 2s代入得到a b nL 2(a b) nL a b这个式子的意思是慢指针在环内走过的整数圈数n 圈等于“链表头到环入口的距离加上入环后到相遇点的距离”。更常用的是把它改写成a nL - b因为 L b c所以又可以写成a (n - 1)L c这个形式特别重要。它说明从链表头走到环入口的距离 a与从相遇点绕若干圈再走 c 步到达环入口的路线在“需要走的路程”上完全等价。换句话说从头部出发走 a 步到达环入口从相遇点出发先绕 (n-1) 圈再走 c 步也正好到达环入口。2.2 重置后二次相遇的几何解释重置操作是这样做的第一次相遇后让其中一个指针回到链表的头节点另一个指针留在相遇点然后两个指针都改成每次走一步同时前进。根据上面的推导从头节点出发的指针走 a 步后到达环入口从相遇点出发的指针走 a 步相当于走了(n-1)L c步也就是绕了 (n-1) 圈后正好从相遇点方向走 c 步回到环入口。所以两个指针会在走完 a 步的那一刻同时停在环入口。这就是“第二次相遇的位置就是环入口”的数学来源。理解这个推导的时候不要把 n 想成需要知道的具体数字。n 是快指针多绕的圈数可能是一圈、两圈或者更多我们不需要知道具体值。推导的意义在于证明“从两个方向同时出发以相同步速前进会在环入口这个位置交汇”这个结论对所有满足条件的链表都成立。2.3 细节到底重置哪个指针其实无所谓大多数资料里写的是“把快指针重置到头节点”所以很多人误以为必须重置 fast。实际上重置慢指针、让快指针留在相遇点效果完全一样。代码里甚至可以写成这样# 方案一fast 回到头节点 fast head while slow ! fast: slow slow.next fast fast.next return slow# 方案二slow 回到头节点 slow head while slow ! fast: slow slow.next fast fast.next return slow两种写法都能正确找到环入口。原因在于推导中的 a 和 c 在模环长意义下是相等的重置谁只是一个对称操作。唯一必须保证的是重置之后两个指针必须同步、同速也就是都走一步不能再让其中一个走两步。否则第二次相遇的位置就会改变。这里还有一个容易踩的坑如果链表头节点本身就是环入口也就是整条链表从头就形成一个完整环那么在第二次循环开始之前被置回头部的指针和留在相遇点的指针可能已经相等比如相遇点正好也是头节点。这种情况下while slow ! fast的循环体不会执行直接返回当前节点结果依然正确。所以你不需要针对这种特殊情况写额外的判断。2.4 两个关键推论环长与“无需重置”的判断推导带来的第一个推论是环长很好求。找到环入口之后从入口出发沿着next走一圈边走边计数回到入口时得到的步数就是环长。因为入口是环的第一个节点从这个点出发走完整环正好一圈。第二个推论更重要如果题目只要求判断链表是否有环不需要定位入口那么第一次相遇之后直接返回存在环即可完全不需要执行重置和第二次遍历。很多初学者把两段代码混在一起看到题目要求“只判断是否存在环”也傻乎乎地去重置指针白白浪费 O(n) 时间。这不是正确性问题而是理解需求边界的问题。3. 场景辨析找环思想什么时候能用、什么时候只是长得像3.1 单向链表场景检测环与求环入口最典型的场景当然是单向链表。面试题里常见的组合是判断链表是否有环要求空间复杂度 O(1)。对应经典题目里编号 141 的那道。判断链表是否有环并且返回环入口节点。对应编号 142 的那道。这两个场景直接使用快慢指针。一个关键辨析是只判环只需要一次相遇定位入口才需要第二次循环。如果你被要求“只判断是否存在环”就不要去重置指针更不要试图返回某个节点否则边界条件会多出一堆。还有一个容易混淆的点判断一个链表是否“相交”时初学者容易想到快慢指针。但链表相交问题描述的是两个独立的链表在某个节点汇合而不是单个链表成环。处理相交题的正确思路是双指针同时遍历或者用哈希集合也可以先把两个链表尾节点对齐比较。快慢指针在这种场景里不能直接套因为两个链表汇合之后不会形成闭环。3.2 数组映射场景找重复数背后的函数图快慢指针并不只活在链表里。有一个非常经典的变体是“给定一个长度为 n1 的数组数字范围在 1 到 n存在一个重复数字要求不修改数组、只用常数空间找出来”。典型题目编号是 287。它的做法是把数组当成一个函数图从索引 i 出发下一个位置是 nums[i]。因为数组中存在重复数字必然会有两个索引指向同一个值而这个值本身又可以作为下一个索引于是从索引 0 出发的路径最终会进入一个环。用快慢指针找到环入口环入口索引就是重复数字。举一个简单的例子nums [1, 3, 4, 2, 2]。从索引 0 出发的路径是这样的0 - 1 - 3 - 2 - 4 - 2 - 4……路径进入2和4形成的循环而重复的数字正好是入口位置 2 对应的值。这个场景和链表的场景本质上是一致的区别只在于“节点”和“指针”换成了“数组索引”和“数组元素值”。理解了这一点代码迁移非常自然。3.3 序列迭代场景快乐数与循环周期检测另一个同构的问题是“快乐数”。给定一个正整数反复执行“把每一位数字平方后求和”的操作如果最终能变成 1就认为它是快乐数如果这个过程陷入循环则不是快乐数。这个问题的状态转移是确定性的一个数字只对应唯一的“下一位数字平方和”所以从任意数字出发都只会走一条路径。如果这条路径进入循环用快慢指针就能检测出来。快指针每次做两次平方和计算慢指针每次做一次两者相遇就说明进入了循环。这个场景的意义在于说明快慢指针找环的本质不是链表专属而是适用于所有“由一个集合上的确定性函数驱动的轨迹”。只要能从当前状态唯一计算出后继状态并且状态空间有限那么从某个起点出发要么终止要么进入环。这类结构在数学上叫函数图快慢指针是检测函数图上环的标准工具。想要更直观地理解可以把这类问题想象成一台自动售货机每次投入固定的按钮组合永远只吐出同一种零食组合。如果你反复按同一个按钮输出序列只可能是“一路不重复”或者“绕圈子重复”两种情况绝不会出现第三种选择。3.4 三类容易误用快慢指针的问题第一类判断链表是否相交。上面已经说过相交链表是两条路径汇合不是一条路径成环快慢指针在这里没有用武之地。第二类求无环链表的中间节点。这个场景确实可以用快慢指针快指针两步、慢指针一步快指针到末尾时慢指针正好停在中间。但这里的核心目的是“找中点”不是“找环”两者代码长得像逻辑完全不同。如果你在一个存在环的链表上直接套“快指针到末尾”的逻辑就会死循环。第三类有向图或者无向图判环。快慢指针只适用于每个节点最多一个后继的情况。一旦一个节点有多个后继路径就不再是唯一的两个指针的追赶关系就不再成立。此时应该用拓扑排序、深度优先搜索或者并查集。这一点在实际项目中特别重要因为业务系统里的状态机往往一个状态有多个出口千万别拿快慢指针去硬套。场景是否适合快慢指针找环正确工具单向链表成环检测适合快慢指针定位环入口适合快慢指针 重置数组中的重复数适合快慢指针函数图快乐数/序列周期检测适合快慢指针链表相交不适合哈希表 / 双指针拼接无环链表中点需要调整快慢指针快到末尾有向图判环不适合拓扑排序 / DFS无向图判环不适合并查集 / DFS4. 手把手实现从“只会判断”到“能定位入口”4.1 最小实现只判断是否有环先用 Python 写出标准的最小实现。定义一个链表节点class ListNode: def __init__(self, val0, nextNone): self.val val self.next next然后是判断是否有环的版本def has_cycle(head: ListNode) - bool: if not head or not head.next: return False slow head fast head while fast and fast.next: slow slow.next fast fast.next.next if slow fast: return True return False这里有一个非常容易踩的坑循环体内必须先移动指针再判断是否相等。如果把比较放在移动之前那么第一步时slow fast都等于 head函数会直接返回 True而空链表或者单节点链表也会被误判成有环。先移动后比较的意义在于两个指针只有在至少移动过一次之后才会产生位置差。循环条件写成while fast and fast.next目的是保证fast.next.next这一行不会访问到空指针。如果fast本身为 None说明快指针已经走到链表末尾如果fast.next为 None说明下一步无法再走两步。两种情况都应当退出循环并判定无环。4.2 完整实现定位环入口与计算环长需要返回环入口时在第一次相遇后加入重置逻辑。下面这个版本可以直接跑def detect_cycle(head: ListNode) - ListNode: slow head fast head while fast and fast.next: slow slow.next fast fast.next.next if slow fast: fast head while slow ! fast: slow slow.next fast fast.next return slow return None如果你还想顺带求出环长可以在找到入口之后再加一次遍历def cycle_length(entry: ListNode) - int: count 1 current entry.next while current ! entry: current current.next count 1 return count求环长跟前述推导没有冲突入口确定后第一次回到入口时走过的步数就是环长。注意环长至少为 1所以计数从 1 开始。4.3 代码里的边界细节与惯用写法很多面试准备者会纠结一个细节第一次相遇后重置的是 fast那有没有可能 fast 重置回 head 之后还没走到环入口就与 slow 相遇了不会。因为根据数学推导二者需要走 a 步才会在环入口相遇而在此之前它们各自的轨迹没有共同节点。你可以自己举一个 a 远小于 c 的例子验证比如 head 到入口 2 步环长 4第一次相遇在入口两站之后的位置重置后前一次循环不会相遇走 2 步后双双停在入口。另一个细节是循环条件的顺序。前面那个版本里第二次循环我直接写while slow ! fast没有检查是否为空。这是因为两个指针都在环内或通往环的路上必然能在遇到空指针之前相遇。如果你在第二次循环里加了空指针判断反而会让代码变得绕。这也是“理解推导之后写代码”和“照抄模板写代码”的区别。Java 版本的核心逻辑完全相同只是换了语法。如果面试官要求用 Java 写直接保持同样的算法骨架把 ListNode 写成 class把None换成null即可。不需要额外改写任何数学关系。5. 实战排查与经验笔记快慢指针的坑都在哪里5.1 死循环什么时候判断条件会失效我第一次写这个算法时遇到过一个很典型的死循环快指针每次走三步。当时我觉得“走更快不是更好吗”结果某个用例就卡死了。原因在上面已经分析过相对速度变成 2 之后存在环长和初始距离配对不当导致永远差一点追上的情况。从那以后我再也不乱改步长比例遇到这类题默认“快二慢一”除非题目明确允许自定义步长。另一个死循环原因是循环条件里漏了fast.next的判断。如果链表是head - 1 - 2 - 3 - None这种无环结构fast会依次走到 0、2、4……当fast为 None 时如果循环条件只写了while fast循环体会执行fast.next.next直接报空指针。正确条件是while fast and fast.next顺序别写反。5.2 “相遇点不是入口”的困惑与验证很多初学者第一次学完后会认为第一次相遇节点就是环入口然后拿几个用例一验发现不对就开始怀疑推导。实际上第一次相遇点只是“快指针追上慢指针”的位置它的特殊性只在于满足a b nL而不是直接等于入口。用一个简单链表验证链表顺序为1 - 2 - 3 - 4 - 5 - 6 - 3其中节点 3 是环入口。此时 a 2b 2从 3 走到 5 需要经历 3-4-5 两步环长 L 4。第一次相遇发生在节点 5。显然节点 5 不是环入口 3。重置后一个指针从 1 出发另一个从 5 出发各走两步后都到达 3第二次相遇才是入口。建议在纸上把这个例子完整推一遍比看十篇文章都有效。你自己跑一遍之后就会彻底明白“重置”的目的是什么。5.3 面试题的边界用例清单面试前可以自己准备一组边界用例快速验证代码是否正确用例期望输出空链表 headNone无环单节点 head.nextNone无环单节点自环 head.nexthead环入口是 head两个节点尾指向头环入口是 head长链尾部接中段节点正确返回中段那个入口整个链表就是完整环环入口是 head无环链表多个节点无环其中“整个链表就是完整环”这个用例很值得单独验证因为 a0第一次相遇点可能就是 head 本身也可能是环内其他节点。无论哪种情况重置后第二次循环都能直接或间接返回 head。如果你在第二次循环之前加了多余判断反而会在这种用例上出错。5.4 复杂度分析与工程选择快慢指针找环的时间复杂度是 O(n)空间复杂度是 O(1)。这里的 n 是链表节点总数。严谨一点说慢指针从 head 走到入环点需要 a 步入环后到第一次相遇最多再走 L-1 步因此总步数和 aL 同阶而 aL 不会超过 n 的常数倍。快指针的步数是慢指针的两倍仍然在 O(n) 范围内。重置之后到第二次相遇两个指针又各走 a 步同样是 O(n) 量级。空间复杂度 O(1) 是它最大的竞争优势。如果用哈希表记录访问过的节点能在 O(n) 时间内返回入口但空间复杂度也是 O(n)。在链表很长、内存受限的工程环境里快慢指针这种“原地判环”的方案更可靠。代价是它需要能够访问节点的引用并且对链表结构有“每个节点最多一个后继”的约束要求。真实业务里的图结构很少能满足这一点所以通常只在链表和函数图场景里使用。我自己在实际使用中还有一个小习惯写完代码以后刻意用一个环长和 a 都为偶数的用例跑一遍再用一个环长为奇数、a 为奇数的用例跑一遍。这两种情况最容易暴露出“快指针跳过相遇点”或者“重置后相遇位置漂移”的逻辑错误。把这个动作变成肌肉记忆面试节奏会稳很多。
搞过链表算法的人一定绕不开“快慢指针找环”这个经典题。我第一次理解“重置快/慢指针”这套操作时确实觉得它有点魔法两个指针明明已经在环里相遇了把其中一个放回链表头部然后都改成一步一步走再相遇的位置居然就是环入口。后来我花了不少时间把背后的数学推清楚才意识到这套操作不是什么奇技淫巧它背后是明确的路程关系和几何含义。这篇文章就把这套逻辑彻底拆开。从“快慢指针为什么能相遇”讲起把重置指针那一步的数学证明展开给你看再辨析哪些场景适合用找环思路、哪些问题只是看着像但完全不是一回事。不管你是刚接触链表的初学者还是准备面试想补深度的开发者这篇应该都能帮你把“会背代码”变成“真正懂原理”。1. 快慢指针为什么能相遇从“相对速度差”理解找环1.1 链表环问题的基础模型先把问题限定清楚。单向链表中每个节点只有一个next指针所谓“有环”就是某个节点的next指向了链表中更早出现的节点于是沿着next一直走就永远走不到尽头。经典的判环题目要求只返回是否存在环进阶一点要求返回环的入口节点。快慢指针的玩法就是让两个指针从头节点出发慢指针每次移动一步快指针每次移动两步。如果链表无环快指针会提前走到尾部指向空循环自然结束如果链表有环两个指针最终会在环内某个节点相遇。这个思路的朴素类比就是两个人在环形跑道上跑步速度快的人经过足够长的时间一定会追上速度慢的人。放到链表里因为环是封闭的快指针一旦进入环早晚会从后面赶上慢指针。这里有个很多人没细想的前提为什么是快指针走两步、慢指针走一步而不是一个走三步一个走一步这需要从相对速度的角度去解释而不是简单背结论。1.2 为什么快指针恰好要走两步先设环的长度为 L。当慢指针刚进入环的时候快指针可能已经处在环内某个位置上。如果把“快指针距离慢指针还差多少步追上”记作 d那么 d 的取值范围是 1 到 L-1。之后每一轮循环快指针相对慢指针前进2 - 1 1步。也就是说两个指针之间的距离每轮稳定缩小 1最多经历 L-1 轮距离必然变成 0也就是追上。如果换成快指针每次走三步、慢指针走一步相对速度就变成 2。每一轮距离缩小 2看起来更快但这里存在一个隐患在环形轨迹上距离是模 L 计算的缩小 2 可能直接“跳过”相遇点。举个反例假设 L6某一时刻快指针落后慢指针 3 步那么距离变化序列是 3、1、5、3、1、5……永远到不了 0。换句话说快指针走三步慢指针走一步在某些环长和初始距离下理论上永远追不上。所以“快两步慢一步”不是拍脑袋定的它保证相对速度为 1使得“追上”这件事必然发生而且不会跳过。这是快慢指针找环算法的根基后面所有重置逻辑都建立在这个前提上。1.3 相遇点的本质一段可以“翻译”成等式的位置第一次相遇之后慢指针并没有走完整个环它可能只走了环长的一部分。这个相遇点本身没有特殊的“魔力”它只是恰好满足了某个路程数量关系。理解这个关系是理解重置操作的关键。假设链表头节点到环入口的距离为 a环入口沿着next方向到第一次相遇点的距离为 b相遇点继续沿着next方向走回环入口的距离为 c。那么环长 L b c。第一次相遇时慢指针走过的总路程 s a b因为慢指针进入环之后从环入口走到相遇点走了 b。快指针走过的总路程 f a b nL其中 n 是快指针在环内比慢指针多绕的圈数n 至少为 1。由于快指针速度是慢指针的两倍存在等式 f 2s。代入之后会得到一个非常漂亮的式子这个式子就是下一节推导的核心。2. 重置快/慢指针的数学推导环入口不是猜出来的2.1 相遇时的路程方程组把上一节的路程关系写成方程组慢指针s a b快指针f a b nL速度关系f 2s代入得到a b nL 2(a b) nL a b这个式子的意思是慢指针在环内走过的整数圈数n 圈等于“链表头到环入口的距离加上入环后到相遇点的距离”。更常用的是把它改写成a nL - b因为 L b c所以又可以写成a (n - 1)L c这个形式特别重要。它说明从链表头走到环入口的距离 a与从相遇点绕若干圈再走 c 步到达环入口的路线在“需要走的路程”上完全等价。换句话说从头部出发走 a 步到达环入口从相遇点出发先绕 (n-1) 圈再走 c 步也正好到达环入口。2.2 重置后二次相遇的几何解释重置操作是这样做的第一次相遇后让其中一个指针回到链表的头节点另一个指针留在相遇点然后两个指针都改成每次走一步同时前进。根据上面的推导从头节点出发的指针走 a 步后到达环入口从相遇点出发的指针走 a 步相当于走了(n-1)L c步也就是绕了 (n-1) 圈后正好从相遇点方向走 c 步回到环入口。所以两个指针会在走完 a 步的那一刻同时停在环入口。这就是“第二次相遇的位置就是环入口”的数学来源。理解这个推导的时候不要把 n 想成需要知道的具体数字。n 是快指针多绕的圈数可能是一圈、两圈或者更多我们不需要知道具体值。推导的意义在于证明“从两个方向同时出发以相同步速前进会在环入口这个位置交汇”这个结论对所有满足条件的链表都成立。2.3 细节到底重置哪个指针其实无所谓大多数资料里写的是“把快指针重置到头节点”所以很多人误以为必须重置 fast。实际上重置慢指针、让快指针留在相遇点效果完全一样。代码里甚至可以写成这样# 方案一fast 回到头节点 fast head while slow ! fast: slow slow.next fast fast.next return slow# 方案二slow 回到头节点 slow head while slow ! fast: slow slow.next fast fast.next return slow两种写法都能正确找到环入口。原因在于推导中的 a 和 c 在模环长意义下是相等的重置谁只是一个对称操作。唯一必须保证的是重置之后两个指针必须同步、同速也就是都走一步不能再让其中一个走两步。否则第二次相遇的位置就会改变。这里还有一个容易踩的坑如果链表头节点本身就是环入口也就是整条链表从头就形成一个完整环那么在第二次循环开始之前被置回头部的指针和留在相遇点的指针可能已经相等比如相遇点正好也是头节点。这种情况下while slow ! fast的循环体不会执行直接返回当前节点结果依然正确。所以你不需要针对这种特殊情况写额外的判断。2.4 两个关键推论环长与“无需重置”的判断推导带来的第一个推论是环长很好求。找到环入口之后从入口出发沿着next走一圈边走边计数回到入口时得到的步数就是环长。因为入口是环的第一个节点从这个点出发走完整环正好一圈。第二个推论更重要如果题目只要求判断链表是否有环不需要定位入口那么第一次相遇之后直接返回存在环即可完全不需要执行重置和第二次遍历。很多初学者把两段代码混在一起看到题目要求“只判断是否存在环”也傻乎乎地去重置指针白白浪费 O(n) 时间。这不是正确性问题而是理解需求边界的问题。3. 场景辨析找环思想什么时候能用、什么时候只是长得像3.1 单向链表场景检测环与求环入口最典型的场景当然是单向链表。面试题里常见的组合是判断链表是否有环要求空间复杂度 O(1)。对应经典题目里编号 141 的那道。判断链表是否有环并且返回环入口节点。对应编号 142 的那道。这两个场景直接使用快慢指针。一个关键辨析是只判环只需要一次相遇定位入口才需要第二次循环。如果你被要求“只判断是否存在环”就不要去重置指针更不要试图返回某个节点否则边界条件会多出一堆。还有一个容易混淆的点判断一个链表是否“相交”时初学者容易想到快慢指针。但链表相交问题描述的是两个独立的链表在某个节点汇合而不是单个链表成环。处理相交题的正确思路是双指针同时遍历或者用哈希集合也可以先把两个链表尾节点对齐比较。快慢指针在这种场景里不能直接套因为两个链表汇合之后不会形成闭环。3.2 数组映射场景找重复数背后的函数图快慢指针并不只活在链表里。有一个非常经典的变体是“给定一个长度为 n1 的数组数字范围在 1 到 n存在一个重复数字要求不修改数组、只用常数空间找出来”。典型题目编号是 287。它的做法是把数组当成一个函数图从索引 i 出发下一个位置是 nums[i]。因为数组中存在重复数字必然会有两个索引指向同一个值而这个值本身又可以作为下一个索引于是从索引 0 出发的路径最终会进入一个环。用快慢指针找到环入口环入口索引就是重复数字。举一个简单的例子nums [1, 3, 4, 2, 2]。从索引 0 出发的路径是这样的0 - 1 - 3 - 2 - 4 - 2 - 4……路径进入2和4形成的循环而重复的数字正好是入口位置 2 对应的值。这个场景和链表的场景本质上是一致的区别只在于“节点”和“指针”换成了“数组索引”和“数组元素值”。理解了这一点代码迁移非常自然。3.3 序列迭代场景快乐数与循环周期检测另一个同构的问题是“快乐数”。给定一个正整数反复执行“把每一位数字平方后求和”的操作如果最终能变成 1就认为它是快乐数如果这个过程陷入循环则不是快乐数。这个问题的状态转移是确定性的一个数字只对应唯一的“下一位数字平方和”所以从任意数字出发都只会走一条路径。如果这条路径进入循环用快慢指针就能检测出来。快指针每次做两次平方和计算慢指针每次做一次两者相遇就说明进入了循环。这个场景的意义在于说明快慢指针找环的本质不是链表专属而是适用于所有“由一个集合上的确定性函数驱动的轨迹”。只要能从当前状态唯一计算出后继状态并且状态空间有限那么从某个起点出发要么终止要么进入环。这类结构在数学上叫函数图快慢指针是检测函数图上环的标准工具。想要更直观地理解可以把这类问题想象成一台自动售货机每次投入固定的按钮组合永远只吐出同一种零食组合。如果你反复按同一个按钮输出序列只可能是“一路不重复”或者“绕圈子重复”两种情况绝不会出现第三种选择。3.4 三类容易误用快慢指针的问题第一类判断链表是否相交。上面已经说过相交链表是两条路径汇合不是一条路径成环快慢指针在这里没有用武之地。第二类求无环链表的中间节点。这个场景确实可以用快慢指针快指针两步、慢指针一步快指针到末尾时慢指针正好停在中间。但这里的核心目的是“找中点”不是“找环”两者代码长得像逻辑完全不同。如果你在一个存在环的链表上直接套“快指针到末尾”的逻辑就会死循环。第三类有向图或者无向图判环。快慢指针只适用于每个节点最多一个后继的情况。一旦一个节点有多个后继路径就不再是唯一的两个指针的追赶关系就不再成立。此时应该用拓扑排序、深度优先搜索或者并查集。这一点在实际项目中特别重要因为业务系统里的状态机往往一个状态有多个出口千万别拿快慢指针去硬套。场景是否适合快慢指针找环正确工具单向链表成环检测适合快慢指针定位环入口适合快慢指针 重置数组中的重复数适合快慢指针函数图快乐数/序列周期检测适合快慢指针链表相交不适合哈希表 / 双指针拼接无环链表中点需要调整快慢指针快到末尾有向图判环不适合拓扑排序 / DFS无向图判环不适合并查集 / DFS4. 手把手实现从“只会判断”到“能定位入口”4.1 最小实现只判断是否有环先用 Python 写出标准的最小实现。定义一个链表节点class ListNode: def __init__(self, val0, nextNone): self.val val self.next next然后是判断是否有环的版本def has_cycle(head: ListNode) - bool: if not head or not head.next: return False slow head fast head while fast and fast.next: slow slow.next fast fast.next.next if slow fast: return True return False这里有一个非常容易踩的坑循环体内必须先移动指针再判断是否相等。如果把比较放在移动之前那么第一步时slow fast都等于 head函数会直接返回 True而空链表或者单节点链表也会被误判成有环。先移动后比较的意义在于两个指针只有在至少移动过一次之后才会产生位置差。循环条件写成while fast and fast.next目的是保证fast.next.next这一行不会访问到空指针。如果fast本身为 None说明快指针已经走到链表末尾如果fast.next为 None说明下一步无法再走两步。两种情况都应当退出循环并判定无环。4.2 完整实现定位环入口与计算环长需要返回环入口时在第一次相遇后加入重置逻辑。下面这个版本可以直接跑def detect_cycle(head: ListNode) - ListNode: slow head fast head while fast and fast.next: slow slow.next fast fast.next.next if slow fast: fast head while slow ! fast: slow slow.next fast fast.next return slow return None如果你还想顺带求出环长可以在找到入口之后再加一次遍历def cycle_length(entry: ListNode) - int: count 1 current entry.next while current ! entry: current current.next count 1 return count求环长跟前述推导没有冲突入口确定后第一次回到入口时走过的步数就是环长。注意环长至少为 1所以计数从 1 开始。4.3 代码里的边界细节与惯用写法很多面试准备者会纠结一个细节第一次相遇后重置的是 fast那有没有可能 fast 重置回 head 之后还没走到环入口就与 slow 相遇了不会。因为根据数学推导二者需要走 a 步才会在环入口相遇而在此之前它们各自的轨迹没有共同节点。你可以自己举一个 a 远小于 c 的例子验证比如 head 到入口 2 步环长 4第一次相遇在入口两站之后的位置重置后前一次循环不会相遇走 2 步后双双停在入口。另一个细节是循环条件的顺序。前面那个版本里第二次循环我直接写while slow ! fast没有检查是否为空。这是因为两个指针都在环内或通往环的路上必然能在遇到空指针之前相遇。如果你在第二次循环里加了空指针判断反而会让代码变得绕。这也是“理解推导之后写代码”和“照抄模板写代码”的区别。Java 版本的核心逻辑完全相同只是换了语法。如果面试官要求用 Java 写直接保持同样的算法骨架把 ListNode 写成 class把None换成null即可。不需要额外改写任何数学关系。5. 实战排查与经验笔记快慢指针的坑都在哪里5.1 死循环什么时候判断条件会失效我第一次写这个算法时遇到过一个很典型的死循环快指针每次走三步。当时我觉得“走更快不是更好吗”结果某个用例就卡死了。原因在上面已经分析过相对速度变成 2 之后存在环长和初始距离配对不当导致永远差一点追上的情况。从那以后我再也不乱改步长比例遇到这类题默认“快二慢一”除非题目明确允许自定义步长。另一个死循环原因是循环条件里漏了fast.next的判断。如果链表是head - 1 - 2 - 3 - None这种无环结构fast会依次走到 0、2、4……当fast为 None 时如果循环条件只写了while fast循环体会执行fast.next.next直接报空指针。正确条件是while fast and fast.next顺序别写反。5.2 “相遇点不是入口”的困惑与验证很多初学者第一次学完后会认为第一次相遇节点就是环入口然后拿几个用例一验发现不对就开始怀疑推导。实际上第一次相遇点只是“快指针追上慢指针”的位置它的特殊性只在于满足a b nL而不是直接等于入口。用一个简单链表验证链表顺序为1 - 2 - 3 - 4 - 5 - 6 - 3其中节点 3 是环入口。此时 a 2b 2从 3 走到 5 需要经历 3-4-5 两步环长 L 4。第一次相遇发生在节点 5。显然节点 5 不是环入口 3。重置后一个指针从 1 出发另一个从 5 出发各走两步后都到达 3第二次相遇才是入口。建议在纸上把这个例子完整推一遍比看十篇文章都有效。你自己跑一遍之后就会彻底明白“重置”的目的是什么。5.3 面试题的边界用例清单面试前可以自己准备一组边界用例快速验证代码是否正确用例期望输出空链表 headNone无环单节点 head.nextNone无环单节点自环 head.nexthead环入口是 head两个节点尾指向头环入口是 head长链尾部接中段节点正确返回中段那个入口整个链表就是完整环环入口是 head无环链表多个节点无环其中“整个链表就是完整环”这个用例很值得单独验证因为 a0第一次相遇点可能就是 head 本身也可能是环内其他节点。无论哪种情况重置后第二次循环都能直接或间接返回 head。如果你在第二次循环之前加了多余判断反而会在这种用例上出错。5.4 复杂度分析与工程选择快慢指针找环的时间复杂度是 O(n)空间复杂度是 O(1)。这里的 n 是链表节点总数。严谨一点说慢指针从 head 走到入环点需要 a 步入环后到第一次相遇最多再走 L-1 步因此总步数和 aL 同阶而 aL 不会超过 n 的常数倍。快指针的步数是慢指针的两倍仍然在 O(n) 范围内。重置之后到第二次相遇两个指针又各走 a 步同样是 O(n) 量级。空间复杂度 O(1) 是它最大的竞争优势。如果用哈希表记录访问过的节点能在 O(n) 时间内返回入口但空间复杂度也是 O(n)。在链表很长、内存受限的工程环境里快慢指针这种“原地判环”的方案更可靠。代价是它需要能够访问节点的引用并且对链表结构有“每个节点最多一个后继”的约束要求。真实业务里的图结构很少能满足这一点所以通常只在链表和函数图场景里使用。我自己在实际使用中还有一个小习惯写完代码以后刻意用一个环长和 a 都为偶数的用例跑一遍再用一个环长为奇数、a 为奇数的用例跑一遍。这两种情况最容易暴露出“快指针跳过相遇点”或者“重置后相遇位置漂移”的逻辑错误。把这个动作变成肌肉记忆面试节奏会稳很多。
平方复杂度无法被常规优化消除｜TaoToken 统一 Key 通道实测)
