判断链表是否为循环链表的算法

2. 循环链表简介

链表是计算机科学中常见的线性数据结构。每个节点包含两部分：数据域和指针域，指针域指向链表中的下一个节点。

我们通常使用一个 head 指针来指向链表的第一个节点：

在普通链表中，最后一个节点的 next 指针为 null，表示链表结束。

而在循环链表（Circular Linked List）中，最后一个节点的 next 指针并不为 null，而是指向链表中的某个已有节点，从而形成一个环：

3. 使用哈希表判断循环链表

一个直观的想法是：如果链表中存在环，那么在遍历时一定会重复访问到某个节点。

我们可以使用一个哈希表（Hash Table）来记录已访问的节点：

boolean isCircularList(Node head) {
    Set<Node> visited = new HashSet<>();
    Node current = head;

    while (current != null) {
        if (visited.contains(current)) {
            return true; // 遇到重复节点，说明有环
        }
        visited.add(current);
        current = current.next;
    }

    return false; // 正常遍历到底，没有环
}

✅ 时间与空间复杂度分析：

• 时间复杂度：O(n)，因为最多遍历整个链表一次。
• 空间复杂度：O(n)，需要存储所有访问过的节点。

⚠️ 缺点：

虽然逻辑清晰，但空间开销较大，适用于内存不敏感的场景。

4. 快慢指针法（Floyd 判圈算法）

这是一个更高效的解决方案，不需要额外空间，只需要两个指针以不同速度前进：

• slow 每次走一步；
• fast 每次走两步；
• 如果链表存在环，两个指针终会相遇；
• 如果 fast 或 fast.next 为 null，则说明链表无环。

boolean isCircularList(Node head) {
    if (head == null) return false;

    Node slow = head;
    Node fast = head.next;

    while (slow != fast) {
        if (fast == null || fast.next == null) {
            return false; // 遍历到底，无环
        }

        slow = slow.next;
        fast = fast.next.next;
    }

    return true; // 相遇说明有环
}

✅ 时间与空间复杂度分析：

• 时间复杂度：O(n)，最坏情况下两个指针各遍历一次链表。
• 空间复杂度：O(1)，只使用了两个指针，空间固定。

⚠️ 注意事项：

• 初始条件要判断 head 是否为 null；
• fast 和 slow 不能从同一个节点开始，否则第一次循环就会退出；
• 这个算法也被称为 Floyd Cycle Detection Algorithm，在很多图算法中都有应用。

🧠 类比理解：

可以想象 slow 是一个慢跑者，fast 是一个快跑者，如果他们在环形跑道上同时出发，快的最终一定会追上慢的。

5. 两种方法对比总结

方法	时间复杂度	空间复杂度	是否推荐
哈希表法	O(n)	O(n)	❌ 不推荐，空间浪费
快慢指针法	O(n)	O(1)	✅ 推荐，高效优雅

6. 总结

本文介绍了两种判断链表是否为循环链表的方法：

1. 哈希表法：简单直观，但空间复杂度高；
2. 快慢指针法（Floyd 判圈算法）：高效且节省空间，推荐使用。

在实际开发中，尤其是资源受限的场景下，推荐使用快慢指针法。掌握这个算法不仅能解决链表问题，也能扩展到图、树等更复杂结构的环检测问题。