141. 环形链表

我们可以使用经典的 Floyd 判圈算法（快慢指针法） 来高效解决。

🧠 核心思想：快慢指针

• 使用两个指针：
  • slow 每次走 1 步
  • fast 每次走 2 步
• 如果链表中 有环，快指针最终会追上慢指针（在环内相遇）。
• 如果链表 无环，快指针会先到达 null（链表末尾）。

💡 为什么能相遇？
在环中，快指针每次比慢指针多走 1 步，相当于“追赶”。只要存在环，快指针一定会在有限步内追上慢指针。

✅ Java 实现

public class Solution {
    public boolean hasCycle(ListNode head) {
        if (head == null || head.next == null) {
            return false;
        }

        ListNode slow = head;
        ListNode fast = head;

        while (fast != null && fast.next != null) {
            slow = slow.next;         // 走 1 步
            fast = fast.next.next;    // 走 2 步
            if (slow == fast) {
                return true;          // 相遇 ⇒ 有环
            }
        }

        return false; // fast 到达了 null ⇒ 无环
    }
}

⏱️ 复杂度分析

• 时间复杂度：O(n)
  最坏情况下，快指针遍历整个链表一次。
• 空间复杂度：O(1)
  只用了两个额外指针，常数空间。

❗ 注意事项

• 必须检查 fast != null && fast.next != null，避免空指针异常。
• 即使链表只有一个节点，只要它指向自己（head.next == head），也算有环。

🆚 与第 142 题的区别

• 141 题：只判断是否有环 → 返回 true/false
• 142 题：找出环的入口节点 → 返回 ListNode

141 是 142 的前置步骤！