---

Floyd判圈算法详解：如何检测链表中的环并找到环的起点

一、算法概述

Floyd判圈算法（又称龟兔赛跑算法）是解决链表环路检测问题的经典方法。它通过快慢指针（一个快指针每次走两步，一个慢指针每次走一步）来判断链表是否存在环，并在存在环时找到环的起始点。

核心思想：

1. 检测环的存在：快慢指针最终会在环内相遇。
2. 找到环的起点：相遇后，重置一个指针到链表头，两个指针以相同速度前进，再次相遇的点即为环的入口。

---

二、代码逐行解析

ListNode *detectCycle(ListNode *head) {
    ListNode *slow = head, *fast = head;
    bool is_first_cycle = true;

    // 第一阶段：检测链表中是否存在环
    while (fast != slow || is_first_cycle) {
        // 如果快指针到达链表尾部，说明无环
        if (fast == nullptr || fast->next == nullptr) {
            return nullptr;
        }
        fast = fast->next->next; // 快指针每次走两步
        slow = slow->next;       // 慢指针每次走一步
        is_first_cycle = false;  // 标记已离开初始状态
    }

    // 第二阶段：找到环的入口
    fast = head; // 重置快指针到链表头
    while (fast != slow) {
        fast = fast->next; // 快慢指针每次各走一步
        slow = slow->next;
    }
    return fast; // 返回环的入口
}

---

三、详细步骤与原理

1. 第一阶段：检测环的存在

初始化指针

• slow和fast初始都指向头节点head。
• is_first_cycle标记为true，确保第一次循环能进入。

循环移动快慢指针

• 快指针移动：fast = fast->next->next（每次两步）。
• 慢指针移动：slow = slow->next（每次一步）。
• 终止条件：
  • 若fast或fast->next为nullptr，说明链表无环。
  • 若快慢指针相遇（fast == slow），说明存在环。

为什么能检测到环？

• 数学原理：假设环存在，快指针每次比慢指针多走一步，最终会追上慢指针。
• 时间复杂度：O(n)，其中n为链表长度。

---

2. 第二阶段：找到环的起点

重置快指针

• 将fast重新指向头节点head，slow保持在相遇点。

同步移动快慢指针

• 快慢指针每次各走一步，直到再次相遇。
• 相遇点即为环的入口。

数学证明

• 设链表头到环入口距离为a，环入口到相遇点距离为b，环长度为L = b + c（c为相遇点到环入口的距离）。
• 当快慢指针第一次相遇时：
  • 慢指针走了a + b步。
  • 快指针走了a + b + kL步（k为绕环次数）。
  • 由于快指针速度是慢指针的两倍，有：
    (2(a + b) = a + b + kL)
    化简得：
    (a = (k-1)L + c)
• 重置快指针后，快指针走a步到达环入口，慢指针走c + (k-1)L步也到达入口。

---

四、边界情况与示例

1. 链表无环

• 示例：1 -> 2 -> 3 -> nullptr
• 执行过程：
  • 快指针很快遇到nullptr，返回nullptr。

2. 链表有环，头节点是入口

• 示例：1 -> 2 -> 3 -> 1
• 执行过程：
  • 快慢指针在节点1相遇。
  • 重置快指针到头部，两者同步移动一步后相遇于节点1。

3. 链表有环，环较深

• 示例：1 -> 2 -> 3 -> 4 -> 5 -> 2
• 执行过程：
  • 快慢指针在环内某处相遇。
  • 重置快指针后，两者同步移动至节点2（入口）。

---

五、算法复杂度

• 时间复杂度：O(n)
  • 检测环最多需要遍历链表两次。
• 空间复杂度：O(1)
  • 仅使用两个指针，无额外空间。

---

六、常见问题解答

1. 为什么快指针要走两步？

• 保证相遇：快指针每次比慢指针多走一步，确保在环内必然追上。

2. 如何处理空链表？

• 初始检查中，若head为nullptr，直接返回nullptr。

3. 为什么第二阶段能正确找到入口？

• 数学推导：通过公式证明，同步移动的指针最终会在入口相遇。

---