AC218-判断单链表是否存在环

代码实现

// 函数 findloop：判断单链表是否存在环
// 使用 Floyd 判环算法（快慢指针法）
bool findloop(LinkList L) {
    LinkList fast = L, slow = L; // 初始化快慢指针，都指向链表头节点

    // 循环条件：快指针不为空 且 快指针的后继不为空
    while (fast != NULL && fast->next != NULL) {
        slow = slow->next;           // 慢指针每次移动一步
        fast = fast->next->next;     // 快指针每次移动两步

        // 如果快慢指针相遇，说明链表存在环
        if (slow == fast) {
            return true; // 存在环
        }
    }

    // 如果快指针到达链表末尾，说明链表无环
    return false; // 不存在环
}

---

代码逻辑解析

1. 算法原理

使用 Floyd 判环算法（也称为龟兔赛跑算法）： - 设置两个指针：慢指针（乌龟）每次移动一步，快指针（兔子）每次移动两步 - 如果链表无环，快指针会先到达链表末尾 - 如果链表有环，快指针会先进入环并在环内循环，最终追上慢指针

2. 指针移动策略

• slow = slow->next：慢指针每次向前移动一个节点
• fast = fast->next->next：快指针每次向前移动两个节点

3. 循环条件分析

• fast != NULL：确保快指针本身不为空
• fast->next != NULL：确保快指针能够移动两步（访问 fast->next->next）

4. 终止条件

• 有环：快慢指针相遇（slow == fast）
• 无环：快指针到达链表末尾（fast == NULL 或 fast->next == NULL）

---

时间复杂度分析

1. 无环情况

• 快指针遍历整个链表，时间复杂度为 O(n)

2. 有环情况

设： - 链表长度为 n - 环外部分长度为 k - 环内部分长度为 r（n = k + r）

当慢指针进入环时，快指针已经在环内。此时快慢指针之间的距离为 d（0 ≤ d < r）。

由于快指针每次比慢指针多移动一步，所以每轮迭代后两者距离减少 1。最坏情况下需要 r 轮才能相遇。

总时间复杂度： - 慢指针进入环：k 步 - 快慢指针相遇：最多 r 步 - 总计：k + r = n 步

因此，时间复杂度为 O(n)

---

空间复杂度分析

• 只使用了两个指针变量（fast 和 slow）
• 没有使用额外的数据结构

因此，空间复杂度为 O(1)

---

较难理解部分的说明

为什么快慢指针一定会相遇？

数学证明：

假设链表有环，设： - 环外长度为 k - 环内长度为 r - 慢指针进入环时，快指针在环内某位置

设此时快指针领先慢指针距离为 d（0 ≤ d < r）。

由于快指针速度是慢指针的 2 倍： - 每轮迭代，慢指针前进 1 步，快指针前进 2 步 - 相对速度差为 1 步 - 因此每轮快指针相对于慢指针前进 1 步

所以经过 (r - d) 轮后，快指针会追上慢指针。

图解说明：

无环情况：
Head -> 1 -> 2 -> 3 -> 4 -> 5 -> NULL
        ↑              ↑
      slow           fast (到达末尾，结束)

有环情况：
        ┌─────────────────┐
        ↓                 │
Head -> 1 -> 2 -> 3 -> 4 -> 5 -> 6
             ↑    ↑           ↑
            k=2   ↓----------↓
                  环长度 r=4

相遇过程：
第1轮：slow=3, fast=5
第2轮：slow=4, fast=6
第3轮：slow=5, fast=4  
第4轮：slow=6, fast=6 (相遇！)

---

延伸知识点

1. 环检测算法的其他方法

方法一：哈希表法

bool findloop_hash(LinkList L) {
    LinkList p = L;
    HashTable* visited = NULL; // 假设有哈希表实现

    while (p != NULL) {
        if (hash_find(visited, p)) {
            return true; // 节点已访问过，存在环
        }
        hash_insert(visited, p);
        p = p->next;
    }
    return false;
}
// 时间复杂度：O(n)
// 空间复杂度：O(n)

方法二：标记法（修改节点）

bool findloop_mark(LinkList L) {
    LinkList p = L;
    while (p != NULL) {
        if (p->visited == true) {
            return true; // 节点已被标记，存在环
        }
        p->visited = true; // 标记节点
        p = p->next;
    }
    return false;
}
// 时间复杂度：O(n)
// 空间复杂度：O(1)
// 缺点：修改了原链表结构

2. Floyd 算法的扩展应用

找到环的起始节点：

LinkList findLoopStart(LinkList L) {
    LinkList fast = L, slow = L;

    // 第一阶段：判断是否有环
    while (fast != NULL && fast->next != NULL) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) break; // 相遇，存在环
    }

    if (fast == NULL || fast->next == NULL) {
        return NULL; // 无环
    }

    // 第二阶段：找到环的起始点
    slow = L; // 重置慢指针到头节点
    while (slow != fast) {
        slow = slow->next;
        fast = fast->next;
    }

    return slow; // 环的起始节点
}

计算环的长度：

int getLoopLength(LinkList L) {
    if (!findloop(L)) return 0; // 无环

    LinkList fast = L, slow = L;
    // 先找到相遇点
    while (fast != NULL && fast->next != NULL) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) break;
    }

    // 从相遇点开始计数，再次回到相遇点
    int length = 1;
    fast = fast->next;
    while (fast != slow) {
        fast = fast->next;
        length++;
    }

    return length;
}

3. 实际应用场景

• 内存泄漏检测：检测循环引用
• 图论算法：检测有向图中的环
• 操作系统：检测进程调度中的死锁
• 编译器：检测程序控制流图中的循环结构
• 网络协议：检测数据包转发中的路由环路

4. 算法优势总结

1. 空间效率高：只需常数空间
2. 时间效率好：线性时间复杂度
3. 不修改原数据：保持链表结构不变
4. 理论优美：基于数学原理，证明严谨

Floyd 判环算法是计算机科学中的经典算法之一，体现了巧妙利用相对运动解决复杂问题的算法设计思想。