当前位置：首页 > article >正文

【码道初阶】Floyd判圈法个人总结：快慢双指针判断环形列表（适用Leetcode142）

article 2025/2/7 19:36:27

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

一、算法概述

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

核心思想：

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

二、代码逐行解析

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步也到达入口。