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

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

题目背景：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 靠近 slow 1 步

距离是 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

结语：如果对你有帮助，请点赞，关注，收藏，你的支持就是我最大的鼓励！