当前位置：首页 > news >正文

【LeetCode刷题日记】142.环形链表Ⅱ

news 2026/6/6 7:25:58

🔥个人主页：北极的代码（欢迎来访）
🎬作者简介：java后端学习者
❄️个人专栏：苍穹外卖日记，SSM框架深入，JavaWeb
✨命运的结局尽可永在，不屈的挑战却不可须臾或缺！

前言：今天是链表篇章的最后一题，但是对于新手来说，一看题目，就有点胆怯了，这题可以说是纸老虎了，虽然看着不是很简单，其实也不是那么简单，里面需要注意很多细节地方，还有一些简单的推理，所以还是需要重点理解的。

题目背景：LeetCode142

给定一个链表的头节点head，返回链表开始入环的第一个节点。如果链表无环，则返回null。
如果链表中有某个节点，可以通过连续跟踪next指针再次到达，则链表中存在环。为了表示给定链表中的环，评测系统内部使用整数pos来表示链表尾连接到链表中的位置（索引从 0 开始）。如果pos是-1，则在该链表中没有环。注意：pos不作为参数进行传递，仅仅是为了标识链表的实际情况。
不允许修改链表。
示例 1：
输入：head = [3,2,0,-4], pos = 1输出：返回索引为 1 的链表节点解释：链表中有一个环，其尾部连接到第二个节点。
示例 2：
输入：head = [1,2], pos = 0输出：返回索引为 0 的链表节点解释：链表中有一个环，其尾部连接到第一个节点。
示例 3：
输入：head = [1], pos = -1输出：返回 null解释：链表中没有环。
提示：
链表中节点的数目范围在范围[0, 104]内
-105 <= Node.val <= 105
pos的值为-1或者链表中的一个有效索引

题目答案：

public class Solution { 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) {// 有环 ListNode index1 = fast; ListNode index2 = head; // 两个指针，从头结点和相遇结点，各走一步，直到相遇，相遇点即为环入口 while (index1 != index2) { index1 = index1.next; index2 = index2.next; } return index1; } } return null; } }

题目解析：

这题代码看着很简单很少，但是重点是思路，下面我们具体分析：
首先，我们第一个需要判断的就是链表是否有环。这里我们使用快慢指针的方式，分别定义 fast 和 slow 指针，从头结点出发，fast指针每次移动两个节点，slow指针每次移动一个节点，如果 fast 和 slow指针在途中相遇，说明这个链表有环。
为什么fast 走两个节点，slow走一个节点，有环的话，一定会在环内相遇呢，而不是永远的错开呢
这就需要好好解释一下了：首先，既然是快指针，肯定是先进入环中的（因为fast指针每次移动两个节点，为什么是两个节点，后面我们就知道了），fast进入环中之后，那肯定就一直在环中运动，与慢指针也只能是在环中相遇，我们可以用相对运动的方式，此时相对于慢指针，快指针始终以每次一个节点的速度靠近慢指针，此时慢指针相对静止。那么只要是有环，快指针就一定能追上慢指针。我们也可以画图模拟一下过程，随机让fast指针在任意一个节点开始追慢指针，发现最后都是快指针差一个节点追上慢指针。
动态过程如图：
解决了第一个问题之后
那么继续回到题目的要求，要求返回链表开始入环的第一个节点，若链表无环，则返回null（这个已经在第一步解决了）。
假设从头结点到环形入口节点的节点数为x。环形入口节点到 fast指针与slow指针相遇节点节点数为y。从相遇节点再到环形入口节点节点数为 z。如图所示：
那么相遇时：slow指针走过的节点数为:x + y， fast指针走过的节点数：x + y + n (y + z)，n为fast指针在环内走了n圈才遇到slow指针，（y+z）为一圈内节点的个数A。
因为fast指针是一步走两个节点，slow指针一步走一个节点，所以fast指针走过的节点数 = slow指针走过的节点数 * 2：
(x + y) * 2 = x + y + n (y + z)
两边消掉一个（x+y）:x + y = n (y + z)
因为要找环形的入口，那么要求的是x，因为x表示头结点到环形入口节点的的距离。
所以要求x ，将x单独放在左面：x = n (y + z) - y,
再从n(y+z)中提出一个（y+z）来，整理公式之后为如下公式：x = (n - 1) (y + z) + z
这里我们也可以使用从特殊到一般的办法，递归寻找，对n进行赋值，也能发现这一规律。注意这里n一定是大于等于1的，因为 fast指针至少要多走一圈才能相遇slow指针。
由此我们就可以找到入环的第一个节点。如下操作
if (slow == fast) {// 有环 ListNode index1 = fast; ListNode index2 = head; // 两个指针，从头结点和相遇结点，各走一步，直到相遇，相遇点即为环入口 while (index1 != index2) { index1 = index1.next; index2 = index2.next; } return index1; }
同时这里又有一个问题了，为什么n一定是大于等于一呢，就好比跑步一样，一个快的追一个慢的，那么你们要想相遇，就一定是快的跑了一圈之后或者n，之后追到了慢的，毕竟不可能反向跑吧。

易错点：

为什么第一次在环中相遇，slow的步数是 x+y 而不是 x + 若干环的长度 + y呢？
需要注意的是，我们要讨论的是第一次相遇的时候，这时就一定有：
slow 刚进入环的那一刻
环长 = L = y + z
1. slow 刚入环时，位置在哪里
slow 在环入口
fast 已经在环里面某个位置
2. 两者之间的距离
因为 fast 速度是 2 倍，slow 走 x 时，fast 走 2x。所以 fast 已经领先一段距离。
但不管领先多少，距离一定满足：0 ≤ 距离 d ＜ L
不可能 ≥ L，否则 fast 早就多跑一圈了。
两者距离取模后一定0 ≤ d < L
相对速度 1，所以d 步必相遇
d < L →slow 不可能走满一圈
fast 也不需要跑一圈就能追上
3. 接下来开始追
slow 速度：1
fast 速度：2
每走 1 步，fast 靠近 slow1 步
距离是 d，所以只需要d 步就会相遇。
4. 关键来了
因为d ＜ L所以 slow 在环里只走了d 步就相遇了。
也就是说：slow 在环里走的步数 y = d ＜ L
y ＜环长→ slow根本没走完一圈就被追上了。
第一次相遇时，慢指针一定没有走完一圈环，所以它的路程只能是 x+y，不可能带上若干个环。

数学推理：

slow 进环前走的距离：x
环的总长度：n
slow 进环时，fast 距离环入口的长度：k
且k < n（因为在环里）
1. 第一句重点
slow 进环的时候，fast 一定已经在环里了。→ 这个没问题，因为 fast 快。
2.核心推理（重点！）
当 slow刚进环时：
fast 已经在环里某个位置
fast 距离环入口的长度是k
k 一定小于 n
3. 原文最关键一句
fast 走到环入口时，走了 k + n 步那么 slow 应该走了 (k + n)/2 步
因为 fast 速度是 2 倍，路程也是 2 倍。
4. 最关键不等式（决定一切）
因为k < n所以：
(k + n) / 2 < (n + n) / 2 = n
也就是说：
slow 走的距离 < n
n 是一环的长度。
5. 最终结论
slow 还没走完一环，fast 已经回到环入口了！
这意味着：
在 slow 走完第一环之前，fast 必然追上 slow
6. 所以：
第一次相遇时，slow 绝对不可能走完一环
slow 走过的路程一定是 x + y
绝对不可能是 x + 一环 + y