0141. Linked List Cycle

题目信息

题号:
  1. 环形链表

难度:

Easy

主题:

链表、Floyd 快慢指针、对象身份、环检测

原题:

LeetCode 0141

重点:

从“节点身份重复”定义环,再用两个不同速度的指针把访问集合压缩为常量状态

题目重述

给定单链表头节点 head,判断沿 next 不断前进时是否会再次到达同一个节点对象。节点值相同不代表 有环,必须比较节点身份。测试说明中的 pos 只是描述尾节点连回哪个位置,并不是函数参数。进阶要求只 使用 O(1) 额外空间。

自建示例

  • 8 -> 3 -> 5 -> 1,尾节点的 next 指回节点 3:沿链会重复访问同一个 3,返回 true;

  • 三个不同节点的值都为 4,但最后指向 nullptr:返回 false;

  • 单节点的 next 指向自身:返回 true;空链和单节点无环链都返回 false。

C++ 实现

#include <unordered_set>

class Solution {
private:
    bool rememberVisitedNodes(ListNode* head) {
        std::unordered_set<ListNode*> visited;
        for (ListNode* node = head;
             node != nullptr;
             node = node->next) {
            if (!visited.insert(node).second) {
                return true;
            }
        }
        return false;
    }

    bool meetWithDifferentSpeeds(ListNode* head) {
        ListNode* slow = head;
        ListNode* fast = head;

        while (fast != nullptr && fast->next != nullptr) {
            slow = slow->next;
            fast = fast->next->next;
            if (slow == fast) {
                return true;
            }
        }
        return false;
    }

public:
    bool hasCycle(ListNode* head) {
        return meetWithDifferentSpeeds(head);
    }
};

题解

先把“有环”翻译为可检测事件

从头沿唯一的 next 路径前进,只有两种结局:到达 nullptr,说明路径有限且无环;或者再次到达某个 已经见过的节点对象,此后路径会永久重复,说明存在环。最直接的 rememberVisitedNodes 把每个节点地址 放入集合;插入失败就表示同一地址第二次出现。

集合必须存 ListNode*,不能存 val。两个不同节点即使值相同仍可依次出现在一条普通链上;环的定义 是引用结构回到同一对象,而不是数据重复。该方案一次扫描即可判定,时间 O(n),但最坏保存 O(n) 个地址。

不用保存历史,能否制造一个必然相遇的状态

若链表有环,进入环后的运动只剩有限个模环长位置。让 slow 每轮走一步,fast 每轮走两步;两者都 进入环后,快指针相对慢指针每轮前进一步。若环长为 lambda,相对距离按模 lambda 依次增加一, 最多 lambda 轮必有一次变为零,即两个指针指向同一节点。

这里不需要知道环从哪里开始或环有多长。两个指针的位置把“是否访问过”问题转化为“速度差是否在有限环上 追平”,从而删除访问集合。

有环时为何两者都会进入环

从头到环入口的链只有有限长度。慢指针最终进入环;快指针沿同一条 next 路径移动且不会遇到空指针, 所以也会进入。一旦进入,next 永远留在环内。快指针可能在慢指针入环前已经绕行若干次,但这只改变 初始相对位置,不影响每轮相对前进一步的结论。

无环时为何不会误报

有限无环链最终指向 nullptr。快指针每轮走两步,因此迟早出现 fast == nullptr 或 fast->next == nullptr,循环结束并返回假。循环守卫必须同时检查这两个条件,才能安全执行 fast->next->next。

指针从同一点出发为何不立即判真

初始化时 slow == fast == head 只是人为把两个观察者放在起点,不是“沿链再次访问”。代码先各自移动, 再比较;否则任何非空链在零步时都会被误判为有环。

输入结构

第一次移动后

结果路径

空链

守卫失败,不移动

返回 false

单节点无环

fast->next 为空,守卫失败

返回 false

单节点自环

slow、fast 都仍指向该节点

移动后相等,返回 true

多节点有环

两者以速度差一在环中追逐

最迟一圈内相遇

代码对应与主解选择

slow、fast 始终是从头沿真实 next 路径可达的节点,不会产生伪造相遇;指针相等表示对象身份 相同,而非值相等。相遇即可证明存在闭合路径,无需再定位入口。

公开入口采用 Floyd 快慢指针,时间 O(n)、额外空间 O(1)。地址集合方案同为线性时间,定义对应 最直接,适合先建立正确性;快慢指针则利用单链表每个节点只有一个后继的结构,将全部访问历史压缩为两个 位置。两种方案都不修改链表。