LeetCode 面试题 02.08. 环路检测

2024-07-18 HGNULB 约 9 分钟

文章信息 9 个分类 3 个标签

分类

LeetCode CodeTop 中等已解决已掌握 2-5 字节跳动美团程序员面试金典（第 6 版）

题目描述

✅ 面试题 02.08. 环路检测

题意分析

给一条单链表，判断它是否成环；如果成环，还要返回入环的那个节点，而不只是返回一个布尔值。无环时返回空。

「入环节点」的定义是：从头节点出发第一次进入环所到达的节点。链表形状像一个字母 ρ——一条直的尾巴接上一个圈，入环节点就是尾巴与圈的连接处。要注意它由节点身份决定，不是由节点值决定，所以比较必须用引用相等而不是值相等。

题目额外强调「不修改链表」，这就排掉了一类常见的偷懒做法：边走边把 next 置空或者给节点打标记。这条约束是在把你往双指针的方向推。

如果允许额外空间，用一个哈希集合记录访问过的节点，第一个重复出现的节点就是入环点，$O(n)$ 时间 $O(n)$ 空间，思路直白。而面试真正想考的是能否做到 $O(1)$ 空间——这个额外要求正是本题从简单升到中等的原因。

边界要提前想清楚三种：空链表；只有一个节点且不成环；只有一个节点且自己指向自己（此时入环点就是它本身）。此外链表长度和环长都可能是 1，任何依赖「环长大于 1」的推导都要重新检查。

解法：快慢指针

核心思路

先看哈希表做法的瓶颈：它需要为每个访问过的节点存一份引用，空间是 $O(n)$。想降到 $O(1)$，就不能记录「访问过谁」，只能靠两个以不同速度前进的指针之间的相对位置关系来推断结构。

第一步是判环。让 slow 每次走一步、fast 每次走两步。如果无环，fast 会先撞到链表末尾；如果有环，两者都会进入环内，此后 fast 相对 slow 每轮恰好逼近一步，所以它们之间的距离每轮减一，不可能跨过去，必然在有限步内相遇。这就是为什么步长选 1 和 2——差值恰好为 1 才能保证不会「跳过」。

第二步是定位入环点，需要一个简单的推导。设头节点到入环点的距离为 $a$，入环点到相遇点（沿环方向）的距离为 $b$，相遇点再走回入环点的距离为 $c$，环长即 $b + c$。相遇时 slow 走了 $a + b$ 步，fast 走了 $a + b + k(b+c)$ 步（$k \geq 1$ 表示它在环里多绕的圈数）。又因为 fast 的步数恰好是 slow 的两倍，得 $2(a+b) = a + b + k(b+c)$，化简得 $a = k(b+c) - b = (k-1)(b+c) + c$。

这个等式的含义非常直观：从头节点走 $a$ 步到达入环点，等价于从相遇点出发走 $c$ 步再绕 $k-1$ 圈，也落在入环点上。既然两段路程步数相同、终点相同，那么让一个指针从头节点出发、另一个从相遇点出发，两者同速每次走一步，它们必然在入环点第一次相遇。

于是维持的不变量是：第二阶段每走一轮，两个指针距离入环点的剩余步数始终相等（在环上按模环长计）。初始时一个剩 $a$ 步、另一个剩 $c + (k-1)(b+c)$ 步，由等式二者相等；同速前进保持相等；当剩余步数归零时两者同时到达入环点，指针相等，循环终止。

无环的情形自然落在 while 条件上：fast 或 fast.next 为空说明走到了尽头，退出循环返回 null，不需要任何额外判断。

解题步骤

slow 与 fast 都从 head 出发：两者同起点是上面推导的前提，若让 fast 提前一步，$2 \times$ 步数的关系就不成立，第二阶段的等式会整体偏移一位。

循环条件写 fast != null && fast.next != null：fast 每轮要走两步，必须保证这两步都有落脚点。两个判断缺一不可，且顺序不能颠倒——先判 fast.next 会在 fast 为空时直接抛异常。这个条件同时也是「无环」的判定：能退出循环就说明走到了链尾。

先移动再比较：循环体里先执行 slow = slow.next、fast = fast.next.next，之后才判断 slow == fast。如果在移动前比较，初始时两者都等于 head，第一轮就会误判为相遇并返回 head。

相遇后让新指针 p 从 head 出发，slow 留在相遇点：这正是 $a = (k-1)(b+c) + c$ 的直接应用，两段等长的路程从两个起点同时开始。

第二个循环 while (p != slow) 里两者各走一步：同速是关键，任何一方走两步都会破坏「剩余步数相等」的不变量。比较用的是引用相等，比的是节点身份而不是 val。

返回 p：此时 p 与 slow 指向同一个节点，返回哪个都可以，返回 p 语义更清楚（它是从头走过来的那条路径的终点）。

循环正常退出时返回 null：说明 fast 撞到了链尾，链表无环。

以 3 → 2 → 0 → -4 且 -4 指回 2 走一遍。把四个节点依次记作 A(3)、B(2)、C(0)、D(-4)，入环点是 B，环是 B → C → D → B，环长 3，a = 1。

第一阶段。初始 slow = fast = A。第一轮：slow 走到 B，fast 走两步到 C，不等。第二轮：slow 到 C，fast 从 C 走两步经 D 回到 B，不等。第三轮：slow 到 D，fast 从 B 走两步经 C 到 D，此时 slow == fast == D，相遇。

验证一下推导：相遇点是 D，b（B 到 D 沿环）= 2，c（D 回到 B）= 1，恰好 $a = 1 = c$，符合 $k = 1$ 的情形。

第二阶段。p = A，slow = D。p != slow，各走一步：p 到 B，slow 从 D 回到 B。此时 p == slow == B，循环退出，返回 B——正是入环节点，答案正确。

再看无环用例 1 → 2 → null：第一轮 slow 到节点 2、fast 走两步变成 null；回到循环条件，fast == null 不成立，退出，返回 null。以及自环用例（单节点指向自己）：第一轮 slow 和 fast 都回到该节点，相遇；第二阶段 p = head 与 slow 本就相等，第二个循环一次都不进，直接返回它自己，正确。

代码实现

public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;

        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {
                // 相遇后一个指针回到头节点，再同步走即可找到入环点。
                ListNode p = head;
                while (p != slow) {
                    p = p.next;
                    slow = slow.next;
                }
                return p;
            }
        }

        return null;
    }
}

func detectCycle(head *ListNode) *ListNode {
    // 令一个指针回到头节点，两个指针同步前进，再次相遇点即为入环点。
    slow, fast := head, head

    for fast != nil && fast.Next != nil {
        slow = slow.Next
        fast = fast.Next.Next
        if slow == fast {
            p := head
            for p != slow {
                p = p.Next
                slow = slow.Next
            }
            return p
        }
    }

    return nil
}

复杂度分析

时间复杂度：$O(n)$，其中 $n$ 是链表节点数。第一阶段中 slow 进入环后最多再走一个环长就会被 fast 追上，总步数不超过「尾巴长 + 环长」即 $n$；第二阶段两个指针最多各走 $a$ 步，$a < n$。两段都是线性。

空间复杂度：$O(1)$，只用了 slow、fast、p 三个指针，且全程不修改链表结构。这是它相对哈希表解法的唯一但决定性的优势。

关键点总结

快慢指针相遇能判环，靠的是相对速度差为 1：差为 1 时快指针每轮逼近一步，绝不会跨过慢指针；如果把步长改成 1 和 3，差为 2，在偶数长度的环里就可能永远错过。这条道理比记住结论更重要。

入环点的定位建立在 $a = (k-1)(b+c) + c$ 这个等式上，面试时要能当场推一遍而不是只报结论。推导只需要「快指针步数是慢指针的两倍」这一个方程，写在白板上不到三行。

「先移动后比较」是所有同起点快慢指针题的固定写法，否则初始重合会造成假相遇。

循环条件 fast != null && fast.next != null 同时承担了「越界保护」和「无环判定」两个职责，这种一个条件兼顾两件事的写法是链表题的常见简化。

比较指针要用引用相等而非值相等；链表题里节点值可以重复，凡是涉及「是不是同一个节点」的判断都不能退化成比 val。

面试展开路径通常是：先说哈希表 $O(n)$ 空间的直观解，再指出题目要求 $O(1)$，然后给出快慢指针并推导入环点。主动铺这条路径比直接甩出答案更能体现思考过程。

易错点总结

在移动指针之前就比较 slow == fast：两者初始都在 head，第一次判断即成立，1 → 2 → null 这种无环链表会直接返回 head，而正确答案是 null。

循环条件只写 fast != null：1 → 2 → null 时 fast 走到节点 2，fast.next.next 里的 fast.next 为空，立刻抛空指针异常。

两个判断顺序写反成 fast.next != null && fast != null：fast 为空时先访问 fast.next 就崩了，短路求值救不了写反的顺序。

第二阶段让两个指针一快一慢：p 走一步而 slow 仍走两步，3 → 2 → 0 → -4（-4 指回 2）会在环里反复错过，可能永远不相等而死循环。

第二阶段起点选错，让 p 从 head.next 出发：等式 $a$ 的起点被改了，上例会返回 C 而不是 B，整体偏移一个节点。

相遇后把 fast 拉回头节点而 slow 也重置：两个指针都回到起点，第二个循环立即成立并返回 head，只有当入环点恰好是头节点时才碰巧正确。

用 slow.val == fast.val 判断相遇：1 → 1 → null 这类值重复的无环链表会被误判成有环；节点身份和节点值是两回事。

想靠「走的步数超过 n 就算有环」来判环：题目不提供链表长度，需要先遍历一趟求长度，而链表有环时这趟遍历本身就不会终止。

边走边把 next 置为 null 来打标记：确实能测出环，但违反了题目「不修改链表」的要求，面试中会被直接否掉。

只返回布尔值：本题要求返回入环节点，写成 141 的答案会在有环用例上返回 true 而非节点，题都做错了对象。

忽略单节点自环：链表只有一个节点且 next 指向自己时，若第二阶段写成 do-while 强制走一步，p 会绕过入环点走到下一圈，返回值虽然碰巧还是它自己，但同样的写法在长环上就会错位。

相似题目

题目	难度	考察点
142. 环形链表 II	中等	与本题同题，可直接套用
LCR 022. 环形链表 II	中等	与 142 同题
141. 环形链表	简单	只需判断有无环，做完第一阶段即可返回，不用推导入环点
202. 快乐数	简单	把「平方和函数」当作隐式的 `next`，在没有链表结构的迭代序列上判环
287. 寻找重复数	中等	用 `nums[i]` 当指针构造隐式链表，重复数恰好是入环点
457. 环形数组是否存在循环	中等	环还要求方向一致且长度大于 1，需额外校验并做已访问标记剪枝
876. 链表的中间结点	简单	同样是一快一慢，但用于定位中点，无环时快指针到底慢指针恰在中间
19. 删除链表的倒数第 N 个结点	中等	双指针改为同速但固定间隔 n，靠位置差而非速度差定位
234. 回文链表	简单	快慢指针找中点后反转后半段比对，是双指针的组合应用