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

1. 题目描述

题目：
给你一个链表的头节点 head，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。
为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。
注意：pos 不作为参数传递，仅仅是为了标识链表的实际情况。

如果链表中存在环，则返回 true，否则返回 false。

示例 1：

输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。

示例 2：

输入：head = [1,2], pos = 0
输出：true
解释：链表中有一个环，其尾部连接到第一个节点。

示例 3：

输入：head = [1], pos = -1
输出：false
解释：链表中没有环。

提示：

• 链表中节点的数目范围是 [0, 10^4]
• -10^5 <= Node.val <= 10^5
• pos 为 -1 或者链表中的一个有效索引。

2. 理解题意与关键点

环形链表的定义：
链表的最后一个节点的 next 指针不指向 null，而是指向链表中的某个先前已经出现过的节点，从而形成一个环。

难点：

• 不能直接用节点的值判断，因为值可能重复。
• 如果链表很长且有环，遍历会无限循环，必须用某种方法检测到环的存在。
• 要求时间复杂度 O(n)，空间复杂度 O(1) 的解法。

3. 思路演进

方法一：哈希表（直观但空间 O(n)）

思路：
遍历链表，把每个节点存入哈希表（集合），每次访问新节点时检查它是否已经在集合中：

• 如果在，说明有环。
• 如果走到 null，说明无环。

缺点：
需要 O(n) 的额外空间。

代码（伪代码）：

set = new HashSet()
while head != null:
    if set.contains(head):
        return true
    set.add(head)
    head = head.next
return false

方法二：快慢指针（Floyd 判圈算法，空间 O(1)）

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

• 如果链表无环，fast 会先到达 null。
• 如果链表有环，fast 会先进入环，slow 后进入环，由于速度差，fast 最终会追上 slow（在环内相遇）。

为什么一定会相遇：
假设 slow 进入环时，fast 在环中的某个位置，两者相距 \(k\) 步（环长 \(L\)，\(0 \le k < L\)）。
每次移动，fast 追近 1 步（因为 fast 走 2 步，slow 走 1 步，相对速度 1 步/次）。
所以经过 \(k\) 次移动后，fast 追上 slow。

细节：

• 初始时 slow = head, fast = head。
• 循环条件：fast != null && fast.next != null（保证 fast 能走两步）。
• 先移动指针，再判断是否相等（避免初始时 slow == fast 误判）。

4. 详细步骤（快慢指针法）

1. 如果链表为空（head == null），直接返回 false。
2. 初始化 slow = head, fast = head。
3. 进入循环，循环条件为 fast != null && fast.next != null：
   • slow = slow.next（慢指针走一步）
   • fast = fast.next.next（快指针走两步）
   • 检查 slow == fast：
     • 如果相等，说明有环，返回 true
4. 循环结束（即 fast 或 fast.next 为 null），说明无环，返回 false。

5. 举例说明

示例 1：head = [3,2,0,-4], pos = 1（尾部指向节点 2）

初始：
slow 在 3，fast 在 3。

第 1 步：
slow 走到 2，fast 走到 0。
不相等。

第 2 步：
slow 走到 0，fast 走到 2（从 -4 的 next 到 2，因为环存在）。
不相等。

第 3 步：
slow 走到 -4，fast 走到 -4（fast 路径：2→0→-4，slow：0→-4）。
此时 slow == fast，返回 true。

6. 代码实现（Java）

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

7. 复杂度分析

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

8. 总结

• 环形链表判断是链表中的经典问题。
• 快慢指针法（Floyd Cycle Detection）是空间复杂度最优的解法。
• 核心是理解“速度差为 1 时，在环中快指针一定能追上慢指针”。
• 该算法还用于寻找环的入口（LeetCode 142 题），方法是相遇后让一个指针从头开始，两个指针同速前进，再次相遇处即为环入口。

需要我继续讲解「环形链表 II」（找环的入口）这道题吗？这样能完整掌握快慢指针的应用。