好的，我们这次来详细讲解 LeetCode 第 141 题「环形链表」（Linked List Cycle）。

1. 题目描述

题意：
给你一个链表的头节点 head，判断链表中是否有环。
如果链表中存在环，则返回 true；否则返回 false。

示例 1：
输入：head = [3,2,0,-4]，并且 -4 的 next 指向 2（形成环）
输出：true

示例 2：
输入：head = [1,2]，并且 2 的 next 指向 1（形成环）
输出：true

示例 3：
输入：head = [1]，next 为 null
输出：false

进阶：
你能用 O(1) 内存解决此问题吗？

2. 理解问题与环的定义

链表节点定义（题目已给）：

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

有环的意思是：链表中某个节点的 next 指针指向了之前遍历过的某个节点，从而在链表中形成闭环。

3. 思路 1：哈希表法（直观解法）

核心思想：
遍历链表，把每个访问过的节点存入哈希集合。在遍历过程中，如果发现某个节点已经在集合中出现过，说明有环。

步骤：

1. 初始化一个空的哈希集合 visited。
2. 指针 cur 从 head 开始遍历链表。
3. 对于每个节点：
   • 如果 cur 在 visited 中，说明有环 → 返回 true。
   • 否则，将 cur 加入 visited，cur 移动到 next。
4. 如果 cur 变为 nullptr，说明链表无环 → 返回 false。

复杂度分析：

• 时间复杂度：O(n)，每个节点访问一次。
• 空间复杂度：O(n)，最坏情况下存储所有节点。

代码（伪代码）：

def hasCycle(head):
    visited = set()
    cur = head
    while cur:
        if cur in visited:
            return True
        visited.add(cur)
        cur = cur.next
    return False

4. 思路 2：快慢指针法（Floyd 判圈算法 / 龟兔赛跑算法）

目标：满足 O(1) 内存。

核心思想：
使用两个指针，一个慢指针 slow 每次走一步，一个快指针 fast 每次走两步。

• 如果链表无环，fast 会先到达末尾（nullptr）。
• 如果链表有环，fast 会先进入环，slow 后进入环，在环内 fast 最终会追上 slow（相遇）。

为什么一定会相遇？
假设 slow 进入环时，fast 在环中的某个位置，它们之间的距离是 d（环长 L，0 ≤ d < L）。
每走一次，fast 比 slow 多走 1 步，距离 d 会减少 1。
所以经过 d 次移动后，fast 会追上 slow。

步骤：

1. 初始化 slow = head，fast = head。
2. 循环条件：fast 和 fast.next 都不为 null（保证可以走两步）。
3. 每次：
   • slow = slow.next
   • fast = fast.next.next
   • 如果 slow == fast，返回 true（有环）
4. 循环结束（fast 或 fast.next 为 null）则返回 false。

复杂度分析：

• 时间复杂度：O(n)，无环时 fast 先到末尾；有环时，慢指针进入环后在一圈内被追上。
• 空间复杂度：O(1)，只用了两个指针。

代码（伪代码）：

def hasCycle(head):
    if not head:
        return False
    slow = head
    fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            return True
    return False

5. 示例推演（快慢指针）

示例 1：3 -> 2 -> 0 -> -4 -> 2（形成环）

初始：slow = 3, fast = 3

1. slow = 2, fast = 0
2. slow = 0, fast = 2
3. slow = -4, fast = -4（相遇）→ 有环

示例 3：1 -> null

初始：slow = 1, fast = 1

1. fast.next 为 null，循环不进入（或第一次循环后 fast.next 为 null 退出）→ 无环

6. 常见疑问与细节

Q1：为什么快指针走 2 步，而不是 3 步？
走 2 步能保证在环内一定相遇（每次距离减 1）。走 3 步可能跨过慢指针，不一定相遇（但理论上调整步长仍可判环，只是复杂度可能变高）。

Q2：快慢指针起点一样，第一次判断 slow == fast 就为真怎么办？
初始时 slow == fast 在循环开始前，所以第一次移动后再比较。这样不会误判。

Q3：空链表或单节点无环的情况？
fast 或 fast.next 为 null 时会退出循环，返回 false。

7. 总结

• 哈希表法：直观，易理解，但需要 O(n) 额外空间。
• 快慢指针法：O(1) 空间，O(n) 时间，是更优解。
• 核心技巧：快慢指针在环内必然相遇，就像操场跑圈，速度快的人会追上速度慢的人。

这样循序渐进地讲解，你是否理解了「环形链表」的判断方法？