如何判断链表是否有环

题目描述：
给定一个单链表的头节点 head，判断链表中是否有环。链表中节点的结构为：每个节点包含一个值（val）和一个指向下一个节点的指针（next）。如果链表中有某个节点可以通过连续跟踪 next 指针再次到达，则链表中存在环；否则，链表中无环。要求尽可能用较优的时间复杂度和空间复杂度解决。

解题过程循序渐进讲解：

第一步：理解问题与环的定义

• 在普通单链表中，每个节点指向下一个节点，最后一个节点指向 null。
• 如果存在环，则某个节点的 next 指针指向了链表中在它之前的某个节点，导致从该节点出发沿着 next 指针会无限循环，永远无法到达 null。
• 目标：编写函数 hasCycle(head)，返回布尔值。

第二步：暴力解法（不推荐但有助于理解）

• 最直观的想法：遍历链表，记录每个访问过的节点。
• 如果当前节点的 next 指针指向一个已经访问过的节点，说明有环。
• 实现：可以用哈希集合（如 HashSet）存储已访问节点。
• 时间复杂度：O(n)，需要遍历链表一次。
• 空间复杂度：O(n)，最坏情况需要存储所有节点。
• 缺点：空间复杂度高，面试中通常要求优化。

第三步：优化思路——快慢指针法（Floyd判圈算法）

• 核心思想：使用两个指针，一个慢指针（每次走一步），一个快指针（每次走两步）。
• 如果链表中无环，快指针会先到达 null。
• 如果有环，快指针会先进入环，慢指针后进入环；由于快指针每次比慢指针多走一步，在环中快指针最终会追上慢指针（相遇）。
• 数学原理：设环外部分长度为 a，环长度为 b。当慢指针进入环时，快指针已经在环中，且快指针与慢指针的距离（在环上沿着行进方向的距离）为 c（0 ≤ c < b）。之后每次移动，距离 c 减少 1（因为快指针比慢指针多走一步）。因此，经过 c 次移动后，两指针必然相遇。
• 时间复杂度：O(n)，最坏情况是 a 很大且 b 很小，但总移动次数不超过 2n。
• 空间复杂度：O(1)，只用了两个指针。

第四步：快慢指针法的实现细节

1. 初始化：slow = head，fast = head（注意：都从头节点开始）。
2. 循环条件：当 fast != null && fast.next != null 时继续（因为快指针每次走两步，需确保 fast.next 不空才能走第二步）。
3. 每次循环：慢指针走一步 slow = slow.next，快指针走两步 fast = fast.next.next。
4. 判断：如果 slow == fast，说明相遇，返回 true。
5. 循环结束：快指针到达 null，说明无环，返回 false。
   边界情况处理：

• 链表为空（head == null）：直接返回 false。
• 链表只有一个节点且无环：fast.next 为 null，循环不执行，返回 false。
• 链表有环但环很小（如自环）：算法同样有效。

第五步：代码示例（以 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;
    }
}

第六步：扩展问题与变种

1. 如何找到环的入口节点：
   • 在快慢指针相遇后，将一个指针移回头节点，另一个留在相遇点。
   • 两个指针每次都走一步，再次相遇的节点就是环的入口。
   • 数学证明：设相遇点距离入口为 x，头节点到入口距离为 a，环长为 b，有 2(a + x) = a + x + kb（k 为快指针在环中已绕的圈数），推导出 a = (k-1)b + (b-x)，即从头节点到入口的距离等于从相遇点继续走到入口的距离（可能绕圈）。
2. 计算环的长度：
   • 在快慢指针第一次相遇后，固定一个指针，让另一个指针继续走，再次相遇时走过的步数就是环长。
3. 如果链表有环，如何获取环外长度：
   • 先找到环的入口，然后从头节点走到入口的步数即为环外长度。

第七步：总结

• 快慢指针法是判断链表是否有环的最优解法，时间复杂度 O(n)，空间复杂度 O(1)。
• 理解其追及原理是掌握该算法的关键。
• 该算法思想也可用于其他循环检测问题（如检测递归中的循环调用）。