🔗 环形链表

题目来源：141. 环形链表 – 力扣（LeetCode）

---

📌 题目描述

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

• 环的定义：链表中某个节点的 next 指针指向了链表中之前的某个节点，从而形成一个闭环。
• 如果存在环，返回 true；否则，返回 false。

---

✅ 示例解析

示例 1：

• 输入：head = [3,2,0,-4], pos = 1
• 输出：true
• 解释：链表尾部（-4）连接到索引为 1 的节点（即 2），形成环。

示例 2：

• 输入：head = [1,2], pos = 0
• 输出：true
• 解释：尾部（2）连接到头节点（1），形成环。

示例 3：

• 输入：head = [1], pos = -1
• 输出：false
• 解释：只有一个节点，且无环。

---

⚠️ 提示

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

---

💡 解法：快慢指针（Floyd 判圈算法）—— O(n) 时间，O(1) 空间

public class Solution {
    public boolean hasCycle(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        
        while (fast != null && fast.next != null) {
            fast = fast.next.next; // 快指针每次走两步
            slow = slow.next;      // 慢指针每次走一步
            
            if (fast == slow) {    // 快慢指针相遇，说明有环
                return true;
            }
        }
        
        return false; // 快指针到达末尾，无环
    }
}

---

📊 复杂度分析

• 时间复杂度：O(n)
  • 如果无环：fast 指针最多走 n/2 步到达末尾。
  • 如果有环：fast 和 slow 指针在环内最多经过 O(环的长度) 步后相遇。
  • 总体为线性时间。
• 空间复杂度：O(1) ✅
  • 仅使用两个指针 fast 和 slow，无需额外存储。

---

🧩 解题思路

1. 核心思想：快慢指针相遇则有环
   • 使用两个指针：
     • slow：每次移动 1 步。
     • fast：每次移动 2 步。
   • 如果链表无环，fast 指针会先到达末尾（null）。
   • 如果链表有环，fast 和 slow 指针最终会在环内相遇（因为 fast 在追赶 slow）。
2. 为什么快慢指针一定能相遇？
   • 设环的长度为 C，slow 进入环时，fast 已经在环内某处。
   • 此时 fast 和 slow 之间的距离为 d。
   • 由于 fast 每次比 slow 多走 1 步，它们之间的距离每轮减少 1。
   • 经过 d 轮后，fast 会追上 slow，即两者相遇。
   • 因此，只要存在环，快慢指针必然相遇。
3. 代码逻辑详解：java深色版本while (fast != null && fast.next != null)
   • 循环条件：确保 fast.next.next 不会空指针异常。
   • 如果 fast == null 或 fast.next == null，说明已到链表末尾，无环。
   java深色版本fast = fast.next.next; slow = slow.next;
   • 快指针走两步，慢指针走一步。
   java深色版本if (fast == slow) return true;
   • 相遇即返回 true。
4. 举例说明： 对 head = [3,2,0,-4]，环连接到索引 1（即 2）：
   • 初始：fast = 3, slow = 3
   • 第1轮：fast = 0, slow = 2
   • 第2轮：fast = -4, slow = 0
   • 第3轮：fast = 0, slow = -4
   • 第4轮：fast = -4, slow = 2
   • 第5轮：fast = 2, slow = 0
   • 第6轮：fast = 0, slow = -4
   • 第7轮：fast = 2, slow = 2 → 相遇！ → 返回 true ✅
5. 边界处理：
   • 空链表：head == null → fast == null → 循环不执行 → 返回 false。
   • 单节点无环：fast.next == null → 循环不执行 → 返回 false。
   • 单节点有环：head.next = head → fast = head.next.next = head，slow = head.next = head → fast == slow → 返回 true。

---

✨ 为什么叫 Floyd 判圈算法？

该算法由计算机科学家 Robert W. Floyd 提出，也称为“龟兔赛跑”算法（Tortoise and Hare Algorithm）。

• 慢指针像“乌龟”，每次走一步。
• 快指针像“兔子”，每次走两步。
• 如果赛道是环形的，兔子终会追上乌龟。