快慢指针找环全解析：从数学推导到代码实现

搞过链表算法的人，一定绕不开“快慢指针找环”这个经典题。我第一次理解“重置快/慢指针”这套操作时，确实觉得它有点魔法：两个指针明明已经在环里相遇了，把其中一个放回链表头部，然后都改成一步一步走，再相遇的位置居然就是环入口。后来我花了不少时间把背后的数学推清楚，才意识到这套操作不是什么奇技淫巧，它背后是明确的路程关系和几何含义。

这篇文章就把这套逻辑彻底拆开。从“快慢指针为什么能相遇”讲起，把重置指针那一步的数学证明展开给你看，再辨析哪些场景适合用找环思路、哪些问题只是看着像但完全不是一回事。不管你是刚接触链表的初学者，还是准备面试想补深度的开发者，这篇应该都能帮你把“会背代码”变成“真正懂原理”。

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 可能直接“跳过”相遇点。举个反例，假设 L=6，某一时刻快指针落后慢指针 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 数组映射场景：找重复数背后的函数图

快慢指针并不只活在链表里。有一个非常经典的变体是“给定一个长度为 n+1 的数组，数字范围在 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 三类容易误用快慢指针的问题

第一类，判断链表是否相交。上面已经说过，相交链表是两条路径汇合，不是一条路径成环，快慢指针在这里没有用武之地。

第二类，求无环链表的中间节点。这个场景确实可以用快慢指针，快指针两步、慢指针一步，快指针到末尾时慢指针正好停在中间。但这里的核心目的是“找中点”，不是“找环”，两者代码长得像，逻辑完全不同。如果你在一个存在环的链表上直接套“快指针到末尾”的逻辑，就会死循环。

第三类，有向图或者无向图判环。快慢指针只适用于每个节点最多一个后继的情况。一旦一个节点有多个后继，路径就不再是唯一的，两个指针的追赶关系就不再成立。此时应该用拓扑排序、深度优先搜索或者并查集。这一点在实际项目中特别重要，因为业务系统里的状态机往往一个状态有多个出口，千万别拿快慢指针去硬套。

4. 手把手实现：从“只会判断”到“能定位入口”

4.1 最小实现：只判断是否有环

先用 Python 写出标准的最小实现。定义一个链表节点：

class ListNode: def __init__(self, val=0, next=None): 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 = 2，b = 2（从 3 走到 5 需要经历 3->4->5 两步），环长 L = 4。第一次相遇发生在节点 5。显然节点 5 不是环入口 3。重置后，一个指针从 1 出发，另一个从 5 出发，各走两步后都到达 3，第二次相遇才是入口。

建议在纸上把这个例子完整推一遍，比看十篇文章都有效。你自己跑一遍之后，就会彻底明白“重置”的目的是什么。

5.3 面试题的边界用例清单

面试前可以自己准备一组边界用例，快速验证代码是否正确：

其中“整个链表就是完整环”这个用例很值得单独验证，因为 a=0，第一次相遇点可能就是 head 本身，也可能是环内其他节点。无论哪种情况，重置后第二次循环都能直接或间接返回 head。如果你在第二次循环之前加了多余判断，反而会在这种用例上出错。

5.4 复杂度分析与工程选择

快慢指针找环的时间复杂度是 O(n)，空间复杂度是 O(1)。这里的 n 是链表节点总数。严谨一点说，慢指针从 head 走到入环点需要 a 步，入环后到第一次相遇最多再走 L-1 步，因此总步数和 a+L 同阶，而 a+L 不会超过 n 的常数倍。快指针的步数是慢指针的两倍，仍然在 O(n) 范围内。重置之后到第二次相遇，两个指针又各走 a 步，同样是 O(n) 量级。

空间复杂度 O(1) 是它最大的竞争优势。如果用哈希表记录访问过的节点，能在 O(n) 时间内返回入口，但空间复杂度也是 O(n)。在链表很长、内存受限的工程环境里，快慢指针这种“原地判环”的方案更可靠。代价是它需要能够访问节点的引用，并且对链表结构有“每个节点最多一个后继”的约束要求。真实业务里的图结构很少能满足这一点，所以通常只在链表和函数图场景里使用。

我自己在实际使用中还有一个小习惯：写完代码以后，刻意用一个环长和 a 都为偶数的用例跑一遍，再用一个环长为奇数、a 为奇数的用例跑一遍。这两种情况最容易暴露出“快指针跳过相遇点”或者“重置后相遇位置漂移”的逻辑错误。把这个动作变成肌肉记忆，面试节奏会稳很多。