跳到主要内容

LeetCode 141. 环形链表

本节目标

用 Floyd 快慢指针从相对速度判断单链表中是否存在环。

这道题是链表解题框架的第三道母题。问题不要求找环的入口，只需判断从头节点不断沿 next 前进时，是否会重复经过某个节点。

查看原题

题意与约束​

链表可能在任意节点处回连到此前的节点，也可能正常以空指针结束。空链表和单节点无环时都应返回 false；单节点指向自身时应返回 true。

第一反应​

让 slow 每轮走一步、fast 每轮走两步。若链表无环，fast 会先到达 null；若有环，二者进入同一环后，fast 每轮相对 slow 多前进一步，有限个环节点中必然相遇。

相对速度为什么足够​

进入环后只需关心两指针在环上的相对位置。每一轮，快指针相对慢指针缩短一个环上的间隔；间隔按环长度循环，最终必定变为零。这个结论只回答“是否有环”，不需要引入环入口位置的额外推导。

循环条件必须先确认 fast 和 fast.next 都存在，之后才能安全地让快指针前进两步。

代码实现​

C++17
class Solution {
public:
    bool hasCycle(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;
    }
};

复杂度分析​

  • 时间复杂度：O(n)。无环时快指针至多走到末尾；有环时进入环后至多再走一圈即可相遇。
  • 空间复杂度：O(1)，只维护两个移动指针。

常见误区​

  • 用节点值是否重复判断环；不同节点完全可能拥有相同的值。
  • 未检查 fast.next 就让快指针走两步，在线性链表末尾越界。
  • 把本题和“寻找环入口”混为一谈，增加不必要的推导与状态。

模式迁移​

快慢指针的相对速度还能迁移到寻找环入口：相遇后让一个指针从头出发，另一个留在相遇点，两者同速前进。中点、回文链表等题也会用不同速度划分阶段，但不共享本题的判环结论。