环形链表——Floyd判圈的数学证明与入环点推导
环形链表——Floyd判圈的数学证明与入环点推导
适读人群：Java 后端工程师、准备算法面试的同学 | 阅读时长：约22分钟 | 难度：Easy+Medium
开篇故事
141 题检测环、142 题找入环点，这两道题我第一次做的时候觉得挺简单的，用 HashSet 秒了。但面试里碰到这道题的时候，面试官直接说"好的，那不用额外空间呢？"我当时脑子里有 Floyd 判圈算法的印象，但具体推导没有想清楚，说了一半就卡住了。
面试官追问"为什么 slow 和 fast 相遇后，把一个指针放回头，然后两个指针同速走，它们一定会在入环点相遇？"这个问题我答不上来，只能说"我知道结论，但没推导过"。
面试结束后我花了两个小时把这个数学推导写在纸上，把每一步都算清楚了。那次之后我对 Floyd 算法的理解就完全不同了——知道结论和知道为什么，差距是巨大的。
这篇文章把 141 和 142 两道题一起讲，重点在 Floyd 算法的数学推导，保证每一步都有依据，不是背结论。
一、题目解析
题目一：LeetCode 141. 环形链表
给你一个链表的头节点 head，判断链表中是否有环。如果存在环，返回 true；否则，返回 false。
题目二：LeetCode 142. 环形链表 II
给定一个链表的头节点 head，返回链表开始入环的第一个节点。如果链表无环，则返回 null。
示例：
输入：head = [3,2,0,-4], pos = 1（尾节点连接到索引1的节点）
141输出：true
142输出：节点2（索引1的节点，值为2）
输入：head = [1,2], pos = 0
141输出：true
142输出：节点1（索引0的节点）
输入：head = [1], pos = -1
141输出：false
142输出：null考点梳理：
- 环的检测——HashSet 法（有额外空间）vs Floyd 法（O(1) 空间）
- 入环点的计算——Floyd 法的数学推导
- 边界情况：空链表、单节点无环、单节点有环（自身成环）
二、解法一：暴力解法——HashSet 记录访问节点
思路
最直观的想法：遍历链表，用 HashSet 记录已经访问过的节点。如果遇到某个节点已经在 HashSet 里，说明存在环，而这个重复节点就是入环点。
完整代码（141 + 142 统一版本）
// 141: 判断是否有环
class Solution141 {
public boolean hasCycle(ListNode head) {
Set<ListNode> visited = new HashSet<>();
ListNode curr = head;
while (curr != null) {
if (visited.contains(curr)) {
return true; // 已访问过，说明有环
}
visited.add(curr);
curr = curr.next;
}
return false;
}
}
// 142: 找入环点
class Solution142 {
public ListNode detectCycle(ListNode head) {
Set<ListNode> visited = new HashSet<>();
ListNode curr = head;
while (curr != null) {
if (visited.contains(curr)) {
return curr; // 第一次重复出现的节点就是入环点
}
visited.add(curr);
curr = curr.next;
}
return null;
}
}复杂度分析
- 时间复杂度：O(n)。每个节点最多被访问一次。
- 空间复杂度：O(n)。HashSet 最多存储 n 个节点引用。
适用场景
代码直观，容易写对，适合快速验证或对空间没有限制的场景。面试中如果时间紧张，先写这个版本，然后再优化为 Floyd 算法。
三、解法二：Floyd 判圈——快慢指针检测环
思路
Floyd 判圈算法（龟兔赛跑算法）：
slow指针每次走一步fast指针每次走两步- 如果链表有环，fast 一定会在环内追上 slow
- 如果链表无环，fast 会先到达 null
为什么有环时 fast 一定能追上 slow？
设环的长度为 L。当 slow 进入环时，fast 已经在环内某处。此后，每经过一轮循环，fast 相对于 slow 的距离缩短 1（fast 走2步，slow 走1步，相对移动1步）。所以最多经过 L 轮后，fast 必然追上 slow。
完整代码
class Solution {
public boolean hasCycle(ListNode head) {
if (head == null || head.next == null) return false;
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; // fast 到达 null，无环
}
}复杂度分析
- 时间复杂度：O(n)。slow 指针在进入环之前最多走 n-L 步（非环部分），进入环后最多再走 L 步（环的周长），总计 O(n)。
- 空间复杂度：O(1)。只用了两个指针。
四、解法三：最优解法——Floyd 算法找入环点（数学推导）
核心：数学推导
这是整篇文章最重要的部分。很多人知道"相遇后把一个指针放回头，同速走就能找到入环点"，但不知道为什么。
设变量：
- 设从链表头到入环点的距离为
a（非环部分的节点数） - 设入环点到 slow 和 fast 相遇点的距离为
b（沿环方向） - 设相遇点回到入环点的距离为
c（沿环方向） - 环长 L = b + c
第一次相遇时的关系：
slow 走过的总距离：a + b fast 走过的总距离：a + b + n*L（fast 比 slow 多绕了 n 圈，n ≥ 1）
因为 fast 速度是 slow 的 2 倍，所以：
2(a + b) = a + b + n*L
a + b = n*L
a = n*L - b
a = (n-1)*L + (L - b)
a = (n-1)*L + c关键结论：a = (n-1)*L + c
这个等式意味着什么？
从相遇点出发走 c 步，到达入环点。然后再走 (n-1) 圈（每圈 L 步），又回到入环点。总共走了 c + (n-1)*L 步，恰好等于 a 步。
所以：一个指针从相遇点出发，另一个指针从链表头出发，两个指针都以步长1同速前进，它们一定会在入环点相遇。
Mermaid 图——Floyd 算法示意
完整代码（142 题）
class Solution {
public ListNode detectCycle(ListNode head) {
if (head == null || head.next == null) return null;
ListNode slow = head;
ListNode fast = head;
// 第一阶段：找相遇点
boolean hasCycle = false;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) {
hasCycle = true;
break;
}
}
// 无环
if (!hasCycle) return null;
// 第二阶段：找入环点
// 根据数学推导：从 head 和 相遇点 同时出发，步长为1，必在入环点相遇
ListNode finder = head;
while (finder != slow) {
finder = finder.next;
slow = slow.next;
}
return finder; // 或 return slow; 两者相同
}
}复杂度分析
- 时间复杂度：O(n)。第一阶段：slow 走 a+b 步，O(n)。第二阶段：两个指针分别走 a 步（根据推导），O(n)。总计 O(n)。
- 空间复杂度：O(1)。全程只用了常数个指针。
额外思考：n=1 时的情况
最常见的情况是 n=1，即 fast 只多绕了 1 圈。此时：
a = (1-1)*L + c = c入环点到相遇点的距离（c）= 头节点到入环点的距离（a）。
这就是为什么在很多示意图里，从头和从相遇点出发的两个指针恰好"镜像"地走向入环点——因为 n=1 时两段路径等长。
提交结果：时间击败约 100% 用户，空间击败约 95% 用户。
五、举一反三
同类题目
LeetCode 287. 寻找重复数 把数组映射成链表（每个 nums[i] 当作 next 指针），然后用 Floyd 算法找"环的入口"，即重复的数字。这道题是 Floyd 算法在非链表场景的经典应用。
LeetCode 202. 快乐数 判断一个数是否是快乐数。对不是快乐数的数字，序列会进入一个循环，用 Floyd 判圈可以检测。
LeetCode 457. 环形数组是否存在循环 在数组中用快慢指针模拟链表环的检测。
解题模板
Floyd 判圈标准模板：
// 初始化，slow 和 fast 都从 head 出发
ListNode slow = head, 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 finder = head;
while (finder != slow) {
finder = finder.next;
slow = slow.next;
}
return finder; // 入环点六、踩坑实录
坑一：快慢指针初始位置相同导致误判
有人把 slow 和 fast 初始化为 head 和 head.next，理由是"这样第一次检查就不会误判相遇"。但这会引入一个微妙的问题：在单节点自环的情况下（节点的 next 指向自身），这种初始化方式的处理逻辑会复杂化。统一从 head 出发，用 do-while 或者先移动再比较，是更稳健的写法。
坑二：Floyd 第二阶段从 head 出发时忘记重置
第二阶段要把一个指针放回 head，另一个留在相遇点。有人误写成"两个都从 head 出发"，这样两个指针总是同步移动，永远相遇在 head，返回 head——而 head 不一定是入环点。
坑三：n 取值讨论不清楚
有人问"为什么 fast 只多走1圈，万一 fast 多走了好几圈呢？"
数学上多走几圈也成立，推导中 a = (n-1)*L + c 对任意正整数 n 都成立：从相遇点走 a 步，恰好是走了 c 步（到入环点）再走 (n-1) 圈。实现上不需要知道 n 的具体值，数学保证了结果的正确性。
坑四：while 循环条件写错导致 NPE
// 错误写法
while (fast != null) {
fast = fast.next.next; // 如果 fast.next == null，NPE
}
// 正确写法
while (fast != null && fast.next != null) {
fast = fast.next.next;
}必须同时检查 fast 和 fast.next，否则无环时 fast 走到最后一个节点，fast.next.next 会 NPE。
坑五：把节点本身和节点值搞混
判断 slow == fast 用的是对象引用相等（两个指针指向同一个节点对象），而不是 slow.val == fast.val。有些节点值相同但是不同节点，用值比较会误判。
七、总结
141 题是基础，HashSet 和 Floyd 都要会。142 题是这两道题的精华，Floyd 找入环点的数学推导是核心。理解了 a = (n-1)*L + c 这个等式，这道题就彻底透了。
Floyd 算法的使用场景远不止链表，任何具有"状态转移可以映射成节点的跳转"的场景，都可以用 Floyd 来检测循环。287 题（寻找重复数）是非链表场景最经典的应用，强烈建议对照着做一遍。
面试里如果被问到"为什么能找到入环点"，把 a = (n-1)*L + c 的推导说出来，绝对是加分项。
Floyd 算法的数学推导你之前清楚吗？评论区聊聊，觉得有用的话点个在看。