如何判断链表是否有环

题目描述
给定一个链表的头节点，判断该链表中是否存在环。链表中环的定义是：链表中某个节点的 next 指针指向了链表中之前已经访问过的节点，从而形成环状结构。要求实现一个函数，输入为链表头节点，输出为布尔值（true 表示有环，false 表示无环）。

解题思路
判断链表是否有环的经典方法是使用快慢指针（Floyd Cycle Detection Algorithm）。其核心思想是：

1. 设置两个指针，一个慢指针每次移动一步，一个快指针每次移动两步。
2. 如果链表中存在环，快指针最终会追上慢指针（两者相遇）；
3. 如果链表无环，快指针会先到达链表尾部（遇到 null）。

详细步骤

1. 初始化指针

   • 定义两个指针 slow 和 fast，初始均指向头节点。
   • 注意处理空链表（头节点为 null）的情况。

2. 遍历链表

   • 使用循环，条件为 fast != null && fast.next != null（保证快指针可以安全移动两步）。
   • 慢指针每次移动一步：slow = slow.next。
   • 快指针每次移动两步：fast = fast.next.next。

3. 检测相遇

   • 每次移动后检查 slow == fast：
     • 若相等，说明快慢指针相遇，链表有环，返回 true。
     • 若快指针到达链表末尾（fast 为 null 或 fast.next 为 null），说明无环，返回 false。

4. 数学原理

   • 假设环外长度为 a，环内长度为 b。
   • 当慢指针进入环时，快指针已在环中，且快指针相对于慢指针的速度为 1 步/次。
   • 由于环长有限，快指针最多追 b 步即可追上慢指针。

示例代码（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;
    }
}

复杂度分析

• 时间复杂度 O(n)：
  • 无环时，快指针先到达末尾，遍历次数为 n/2。
  • 有环时，最坏情况下慢指针走完环外距离 a 后，快指针需追 b 步（a+b=n），仍为 O(n)。
• 空间复杂度 O(1)：仅使用两个指针。

扩展问题
若需要找出环的入口节点，可在快慢指针相遇后，将慢指针重新指向头节点，然后快慢指针每次均移动一步，再次相遇的节点即为环入口（数学可证）。