环形链表

阅读要点

• Floyd 判环算法使用快慢指针，快指针每次两步，慢指针每次一步。
• 若链表有环，快慢指针一定在环内相遇，且相遇点即为环入口。
• 证明基于相对速度（步差为1）和距离参数 a（头到环入口）、b（环长）、k（入口到相遇点）。
• 代码实现简洁，时间复杂度 O(n)，空间复杂度 O(1)。

题目

141. 环形链表 - 力扣（LeetCode）

解法

最简单的做法是用哈希集合记录出现过的节点，但空间复杂度为 O(n)。本文重点介绍 Floyd 判环算法（龟兔赛跑算法），空间复杂度仅为 O(1)。

核心思想：使用快慢两个指针，从链表头同时出发。慢指针每次走一步，快指针每次走两步。如果链表中有环，快指针最终会追上慢指针，且相遇点即为环的入口。

为何一定相遇

假设链表存在环，快指针和慢指针进入环后，快指针相对于慢指针的速度为 1 步/次（快指针每次比慢指针多走一步）。由于环是有限的，快指针必然在有限步数内追上慢指针。例如，在一个长度为 b 的环中，最坏情况下快指针需要追 b-1 步即可相遇。

为何相遇点就是环入口

设定参数如下：

• a：链表头结点 H 到环入口 E 的距离（步数）。
• b：整个环的长度（步数）。
• k：从环入口 E 出发，沿环的方向走到第一次相遇点 M 的距离（步数），显然 0 ≤ k < b。

推导：

• 当慢指针到达环入口时，它走了 a 步。此时快指针已经走了 2a 步，在环内的位置为 (2a - a) mod b = a mod b。
• 之后，慢指针再走 k 步到达相遇点，此时快指针走了 2k 步，其总步数为 2a + 2k。
• 相遇时，快指针比慢指针多走了整数圈：2a + 2k - (a + k) = a + k = n * b（n 为正整数）。
• 因此 a + k 是 b 的整数倍，即 a ≡ -k (mod b)。这意味着从相遇点 M 再走 a 步会回到环入口 E。
• 所以，将快指针重置到头结点，然后快慢指针都每次走一步，它们将在环入口相遇。

这个结论可以直观理解：从头结点到环入口的距离 a，等于从相遇点沿环方向到环入口的距离（b - k）的整数倍？实际上，由 a + k = n * b 可得 a = n * b - k，即从相遇点逆时针走 k 步到环入口？待补充更直观的解释。

代码

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
 
class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        # 没有节点或只有一个节点
        if not head or not head.next:
            return False
        fast, slow = head, head
        while fast and fast.next and slow:
            fast = fast.next.next
            slow = slow.next
            if fast == slow:
                return True
        return False

扩展思考

如果题目要求返回环的入口节点，可以在检测到相遇后，将快指针重置到头结点，然后快慢指针各走一步，再次相遇的节点即为环入口。代码只需稍作修改。