在单链表中检测环

1. 概述

在本教程中，我们将讨论如何检测一个单链表中是否存在环，并找出环的起始节点。

首先，我们将介绍问题的基本概念，然后讲解两种主流解决方案。接着，我们分析两种特殊情况，并说明如何调整其中一种方法来处理它们。

最后，我们会对所有方法进行对比，帮助你根据实际场景选择最合适的方式。

---

2. 问题定义

假设我们有一个单链表 A，它包含 n 个节点。我们的目标是判断该链表是否包含环（cycle），如果存在环，则找出环的起始节点。

什么是链表中的环？

链表由若干节点组成，每个节点指向下一个节点。当最后一个节点不再指向 null，而是指向链表中的某个已有节点时，就形成了环。

如下图所示：

需要注意：

• 一个链表中只能存在一个环。
• 环的成因一定是最后一个节点指向了链表中已有的某个节点。

---

3. 标记访问法（Visited Approach）

3.1 基本思路

在无环链表中，我们可以使用 while 循环进行遍历：

Node current = head;
while (current != null) {
    // process current node
    current = current.next;
}

但如果链表中存在环，这段代码会陷入死循环。

解决方法：
为每个节点添加一个 visited 标志位，记录是否已被访问过。

3.2 实现代码

public Node detectCycleWithVisited(Node head) {
    Node current = head;
    while (current != null && !current.visited) {
        current.visited = true;
        current = current.next;
    }
    return current; // 若为 null 表示无环
}

✅ 优点：

• 实现简单，逻辑清晰。

❌ 缺点：

• 需要修改节点结构，添加 visited 字段。
• 若链表不可变（如只读），此方法不适用。

⚠️ 注意：
遍历结束后应将所有节点的 visited 标志位重置为 false，避免影响其他逻辑。

---

4. 特殊情况处理

4.1 小范围整型 ID（Small Integer IDs）

如果每个节点有一个整型 ID，且其取值范围较小（如 [0, MaxVal]），我们可以使用一个布尔数组来记录访问状态：

public Node detectCycleWithSmallIds(Node head, int maxVal) {
    boolean[] visited = new boolean[maxVal + 1];
    Node current = head;
    while (current != null) {
        if (visited[current.id]) {
            return current;
        }
        visited[current.id] = true;
        current = current.next;
    }
    return null;
}

✅ 优点：

• 不需要修改节点结构。
• 时间复杂度 O(n)

❌ 缺点：

• 空间复杂度 O(MaxVal)，若 ID 范围大则不适用。

4.2 使用 TreeSet（TreeSet Approach）

当 ID 不是整数或值域很大时，可以使用 TreeSet 或 HashSet 来记录已访问节点：

public Node detectCycleWithTreeSet(Node head) {
    Set<Integer> visited = new TreeSet<>();
    Node current = head;
    while (current != null) {
        if (visited.contains(current.id)) {
            return current;
        }
        visited.add(current.id);
        current = current.next;
    }
    return null;
}

✅ 优点：

• 通用性强，适用于任意类型 ID（只要可比较/可哈希）。

❌ 缺点：

• 时间复杂度 O(n log n)
• 空间复杂度 O(n)

---

5. 双指针法（Two-Pointers Approach）

5.1 基本思路

使用两个指针 slow 和 fast：

• slow 每次移动 1 步
• fast 每次移动 2 步

如果链表中存在环，两个指针最终会相遇。

步骤如下：

1. 判断是否存在环
2. 计算环的长度 m
3. 找出环的起始节点

5.2 实现代码

public Node detectCycleWithTwoPointers(Node head) {
    Node slow = head, fast = head;
    boolean hasCycle = false;

    // Step 1: Check for cycle
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow == fast) {
            hasCycle = true;
            break;
        }
    }

    if (!hasCycle) return null;

    // Step 2: Calculate cycle length
    int m = 0;
    do {
        slow = slow.next;
        m++;
    } while (slow != fast);

    // Step 3: Find start of cycle
    slow = head;
    fast = head;
    for (int i = 0; i < m; i++) {
        fast = fast.next;
    }

    while (slow != fast) {
        slow = slow.next;
        fast = fast.next;
    }

    return slow;
}

✅ 优点：

• 不需要额外空间（O(1)）
• 不修改原始链表结构

❌ 缺点：

• 逻辑较复杂，需要理解数学原理

5.3 原理证明（简要）

• fast 指针速度是 slow 的两倍
• 一旦进入环，fast 会“追上” slow
• 两者相遇后，通过调整指针位置可以找到环的起点

---

6. 方法对比

方法	时间复杂度	空间复杂度	是否修改结构	适用场景
Visited Approach	O(n)	O(n)	✅ 是	可修改节点结构
Small Integer IDs	O(n)	O(MaxVal)	❌ 否	ID 范围小
TreeSet Approach	O(n log n)	O(n)	❌ 否	通用
Two-Pointers Approach	O(n)	O(1)	❌ 否	最通用

---

7. 总结

在检测链表环的问题中，我们有多种解决方案：

• Visited Approach：实现简单，但需要修改节点结构。
• Small Integer IDs：适合 ID 范围小的场景。
• TreeSet / HashSet Approach：通用但效率较低。
• Two-Pointers Approach：最推荐的通用解法，空间效率高，无需修改结构。

✅ 最佳实践建议：

• 若无法修改结构，优先使用双指针法。
• 若 ID 有特殊限制，可考虑小整型或集合法。
• 只有在允许修改结构时才使用 Visited 法。

掌握这些方法后，在实际开发中遇到链表环的问题时就能游刃有余了。