LC142　环形链表 II¶

中等通过率 63.2%python3核心代码模式链表样例通过牛客 AC哈希表链表双指针Floyd 判圈算法

讲解章节：链表

一句话

不只判断有没有环，还要返回环的入口节点，没有环返回 null。

解题思路¶

这题考什么¶

先用 Floyd 判圈算法（龟兔赛跑，slow 一步 fast 两步）找到相遇点，再靠一条等式把入口算出来。设：

a = 表头到环入口的距离
b = 环入口到相遇点的距离（沿环前进方向）
c = 环长

相遇时 slow 走了 a + b 步。fast 速度是两倍，走了 2(a + b) 步；同时 fast 的路径是「先到相遇点，再绕环若干整圈」，即 a + b + kc 步（k >= 1）。两式相等得 a + b = kc，移项得

a = k*c - b = (k - 1)*c + (c - b)

右边的 c - b 正是「从相遇点继续前进到环入口」的距离，前面的 (k - 1)c 是若干整圈。也就是说：从表头走 a 步会到入口，从相遇点走 a 步同样会到入口（多绕的整圈不影响落点）。于是把一个指针放回表头，两个指针同速*每次一步，再次相遇处就是环入口。

这是本题唯一需要推的东西，推完代码只有几行。链表见链表。

数据规模与复杂度¶

节点数最多 10^4，值域 -10^5..10^5。第一阶段 O(a + c)、第二阶段 O(a)，合计 O(n) 时间；只用几个指针，额外空间 O(1)，满足进阶要求。

哈希表做法（边走边把节点丢进 set，第一个重复出现的就是入口）同样 O(n) 时间，写起来更短，但要存最多 10^4 个节点引用，空间 O(n)。两种都能过，这里取常数空间的版本，因为进阶问的正是它。

坑在哪¶

第二阶段两个指针必须同速，都是一步。沿用第一阶段的一快一慢会直接跑飞，上面的推导只保证「同样走 a 步」才同时到达入口；
相遇判断用 is 比身份。链上的值允许重复（题面值域含大量重复的可能），按 val 比会在环外就误判；
无环时必须返回 None 而不是任何节点。fast 或 fast.next 变成 None 就退出，对应样例三的 pos = -1；
第二阶段的循环条件是「两指针不是同一个节点」，起点相同时（a = 0，即表头就是环入口）循环一次都不进，直接返回表头，这是正确答案而不是漏判；
相遇点本身不是环入口。样例一里相遇点是值 -4 的节点，而入口是值 2 的节点，直接返回相遇点会错。

样例复核¶

[3,2,0,-4]，尾节点接回下标 1，故 a = 1、c = 3。第一阶段相遇在下标 3（值 -4），此时 b = 2，验算 a + b = 3 = 1 * c，等式成立。第二阶段：ptr 从表头（值 3）走一步到值 2 的节点，slow 从 -4 走一步也到值 2 的节点，两者相同，返回下标 1 的节点，与样例期望的「索引为 1 的链表节点」一致。

参考实现¶

solutions/leetcode/LC142/sol.py
from typing import List, Optional


class Solution:
    def detectCycle(self, head: "Optional[ListNode]") -> "Optional[ListNode]":
        slow = head
        fast = head
        # 第一阶段：一步与两步的指针在环内必然相遇；无环则 fast 先摸到链尾
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            # 比身份不比 val，链上的值可以重复
            if slow is fast:
                # 第二阶段：由 a = (k-1)*c + (c-b)，从表头和从相遇点同速前进会在入口汇合
                ptr = head
                while ptr is not slow:
                    ptr = ptr.next
                    slow = slow.next     # 两个指针都是一步一格，速度必须相同
                return ptr               # 汇合点即环入口
        # fast 走到 None，链是有限长的直线，没有环
        return None

LC142 环形链表 II¶