跳到主要内容

LeetCode 142. 环形链表 II

本节目标

用 Floyd 快慢指针判环，再由距离关系定位环的入口节点。

查看 LeetCode 原题

题意与边界​

返回单链表进入环的第一个节点；没有环时返回空。题目只把环入口位置用于构造测试数据，不会把位置作为参数传入，并且不允许修改链表。

两次相遇​

慢指针每次走一步，快指针每次走两步。若存在环，它们会在环内相遇。此时让新指针 entry 从头节点出发，并让 slow 从相遇点出发，两者都改为每次一步；下一次相遇的位置就是环入口。

正确性依据​

设头到入口距离为 a，入口到首次相遇点距离为 b，环长为 c。首次相遇时快指针比慢指针多走若干整环，因此 a + b 与 c 的关系推出 a 等于从相遇点继续走到入口的距离再加若干整环。两个一步指针分别从头和相遇点出发，走 a 步后必在入口相遇。

代码实现​

C++17
class Solution {
public:
    ListNode* detectCycle(ListNode* head) {
        ListNode* slow = head;
        ListNode* fast = head;
        while (fast != nullptr && fast->next != nullptr) {
            slow = slow->next;
            fast = fast->next->next;
            if (slow == fast) {
                ListNode* entry = head;
                while (entry != slow) {
                    entry = entry->next;
                    slow = slow->next;
                }
                return entry;
            }
        }
        return nullptr;
    }
};

复杂度分析​

  • 时间复杂度：O(n)，判环和定位入口都只在线性范围内移动。
  • 空间复杂度：O(1)，不使用访问集合。

易错点​

  • 把评测描述中的 pos 当成函数参数。
  • 找到快慢指针相遇点后直接返回；相遇点通常不是入口。
  • 第二阶段仍让快指针一次走两步，破坏距离等式。

模式迁移​

Floyd 算法也可用于有限状态转移中的重复状态检测。先证明必然相遇，再利用周期长度与前缀长度关系定位周期起点，是这一模式的完整两阶段结构。