LC 142. 环形链表 II

题目描述

这是 LeetCode 上的 142. 环形链表 II ，难度为 中等。

给定一个链表的头节点 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, 10^4]$ 内
• $-10^5 <= Node.val <= 10^5$
• pos 的值为 -1 或者链表中的一个有效索引

进阶：你是否可以使用 $O(1)$ 空间解决此题？

---

快慢指针

起始使用 slow 和 fast 作为慢快指针（slow 每次走一步，fast 每次走两步），起始均为 head。

若 fast 顺利走到结尾，说明链表无环，直接返回 null；

若两者成功相遇，说明链表有环。我们定义链表起点到环入口距离为 x，环内节点数量为 y。那么从链表起点到环入口的任意路径都能归纳成 $x + k \times y$（其中 $k$ 为大于等于 $0$ 的任意值）。

当两者首次相遇时，假设 slow 走的距离为 d1，而 fast 走的距离为 d2，根据速度差定义可知 $d2 = d1 \times 2$。同时根据 141. 环形链表 结论，两者必然在环中相遇，且必然是 fast 在环内从后面追上 slow，因此 d2 相比于 d1 必然是多了 y 的整数倍，即有 $d2 = d1 + m \times y$（其中 $m$ 为圈数），即可推导出 $d1 = m \times y$。

同时根据链表起点到环入口的任意路径均表示为 $x + k \times y$，我们知道如果 slow 再走 x 步会到达环入口，同时链表起点到环入口也是 x 步，因此我们可以复用 fast，将其复位到链表起点，和 slow 一起每次往前一步，当两者再次相遇，必然是同时位于环入口。

同时该做法容易拓展成求 x 和求 y 等问题。

代码：

public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode base = head;
        ListNode slow = head, fast = head;
        boolean ok = false;
        while (!ok && fast != null && fast.next != null) {
            slow = slow.next; fast = fast.next.next;
            if (slow == fast) ok = true;
        }
        if (!ok) return null;
        fast = head;
        while (slow != fast) {
            slow = slow.next; fast = fast.next;
        }
        return slow;
    }
}

• 时间复杂度：$O(n)$
• 空间复杂度：$O(1)$

---

最后

这是我们「刷穿 LeetCode」系列文章的第 No.142 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。