LeetCode LCR 022. 环形链表 II

2026-03-28 HGNULB 约 7 分钟

文章信息 5 个分类 4 个标签

分类

LeetCode 中等 119 经典题变种挑战剑指 Offer 剑指 Offer（专项突击版）

题目描述

✅ LCR 022. 环形链表 II

题意分析

给定一条链表，如果它含环，返回入环的第一个节点；不含环则返回空。判定「相同」用的是节点身份而不是节点值，所以整题都要按引用比较。

题目不允许修改链表，这条约束堵死了「走过就把 next 指向自己」之类的破坏性标记法。进阶还要求 $O(1)$ 空间，于是「用哈希集合记录访问过的节点」这个最直观的做法虽然正确，却不是题目最终想要的答案。

剩下能用的信息只有链表本身的形状。含环链表一定长成「一条直尾巴 + 一个圆环」：从头走 a 步到达入环点，环长记为 b + c。走进环里的指针永远出不来，只会一圈圈绕下去，这就为「用速度差把两个指针撞在一起」提供了可能。

边界需要覆盖：空链表、单节点无环、单节点自环（head.next == head，入环点就是 head 自己），以及整条链表本身就是一个环（a = 0）。

解法：双指针收缩边界

核心思路

暴力做法是边走边把节点存进哈希集合，第一个重复出现的节点就是入环点，时间 $O(n)$、空间 $O(n)$。瓶颈就在那份集合上——它保存了全部历史，而我们真正需要的只是一个「是否绕回来过」的信号。

观察：如果一个指针每次走一步、另一个每次走两步，那么每一轮它们的相对距离就缩短 1。慢指针进环之后，快指针在环内从后面追它，距离每轮减一且不会跨过去，因此只要有环就必然相遇；反之若无环，快指针会先走到链尾，用 fast == null || fast.next == null 就能判无环。这一步只用了两个指针，空间降到 $O(1)$。

相遇之后还要把入环点找出来，这才是本题的真正考点。设起点到入环点为 a 步，入环点到相遇点为 b 步，相遇点绕回入环点还需 c 步（环长 b + c）。相遇时慢指针走了 a + b，快指针走了 a + b + k(b + c)（k >= 1 是快指针多绕的圈数），而快指针路程恰是慢指针的两倍，于是 $2(a+b) = a+b+k(b+c)$，整理得 $a = k(b+c) - b = (k-1)(b+c) + c$。

这个等式的含义是：从链表头走 a 步，与从相遇点走 a 步，会停在同一个位置——入环点。因为从相遇点走 c 步就到入环点，多出来的 (k-1) 整圈只是原地打转。所以相遇后让一个新指针从 head 出发、慢指针留在相遇点，两者同速前进，第一次相等的位置就是答案。

由此得到两段循环各自的不变量：第一段维持「fast 走过的步数恒为 slow 的两倍」；第二段维持「answer 到入环点的剩余步数，与 slow 到入环点的剩余步数相等」。

解题步骤

初始化：fast 和 slow 都指向 head。两者同起点，「路程恰好两倍」这个关系才从第 0 步就成立，后面的方程也才有效。

判环循环：条件写 fast != null && fast.next != null。fast 每轮要跳两格，两个位置都可能踩空，缺一个就会在无环链表上抛空指针；条件为假即说明走到了链尾，直接返回空表示无环。

推进与判相遇：先 slow = slow.next、fast = fast.next.next，再比较 slow == fast。顺序必须是「先走后判」——两者初始就相等，若先判会在第一轮直接误报相遇，把 head 当成入环点。

找入环点：相遇后新开 answer = head，与仍停在相遇点的 slow 同速前进，直到 answer == slow，返回 answer。依据就是 $a = (k-1)(b+c) + c$，两个指针每轮各走一步，剩余步数同步递减，必然在入环点相等。

循环自然结束：fast 走到空说明无环，返回 null。

以 3 → 2 → 0 → -4、-4 指回节点 2 走一遍。此时 a = 1（头到入环点 2 一步），环是 2 → 0 → -4 → 2，环长 3。第一轮：slow 到 2，fast 到 0，不等。第二轮：slow 到 0，fast 走两步 -4 → 2 落在 2，不等。第三轮：slow 到 -4，fast 走两步 0 → -4 落在 -4，两者相等，相遇点是节点 -4。

进入第二段：answer = 3（头节点），slow = -4。走一轮 answer 到 2，slow 沿 -4.next 回到 2，两者相等，返回节点 2——正是入环点。

再看 1 → 2、无环：第一轮 slow 到 2、fast 走两步到空，不等；回到循环条件时 fast != null 为假，退出，返回 null，正确。

代码实现

class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode fast = head, slow = head;
        while (fast != null && fast.next != null) {
            // 先推进再判等，避免同起点在第一轮被误判为相遇。
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {
                // a = (k-1)(b+c) + c，头与相遇点同速前进必在入环点相遇。
                ListNode answer = head;
                while (answer != slow) {
                    answer = answer.next;
                    slow = slow.next;
                }
                return answer;
            }
        }
        return null;
    }
}

func detectCycle(head *ListNode) *ListNode {
    fast, slow := head, head
    for fast != nil && fast.Next != nil {
        // 先推进再判等，避免同起点在第一轮被误判为相遇。
        slow = slow.Next
        fast = fast.Next.Next
        if slow == fast {
            // a = (k-1)(b+c) + c，头与相遇点同速前进必在入环点相遇。
            answer := head
            for answer != slow {
                answer = answer.Next
                slow = slow.Next
            }
            return answer
        }
    }
    return nil
}

复杂度分析

时间复杂度：$O(n)$。慢指针进环后，快指针与它的距离每轮减一，最多再走一个环长就追上，第一段总步数是 a + b + c 量级；第二段两个指针各走 a 步。两段都是线性，循环体内只有指针赋值与比较。

空间复杂度：$O(1)$，全程只有 fast、slow、answer 三个引用，不随链表长度增长，也没有递归栈——这正是它相对哈希集合法的核心优势。

关键点总结

「快慢两倍速」把「是否存在环」转换成「两个指针能否相等」，用速度差替代历史记录，是把 $O(n)$ 空间压到 $O(1)$ 的通用手段。

推导 $2(a+b) = a+b+k(b+c)$ 时不要漏掉圈数 k，只写 k = 1 虽然结论相同，但面试官追问「快指针绕了很多圈还成立吗」时会答不上来。

「先推进再判相等」是所有同起点双指针的固定写法，起点相同就意味着判等必须后置。

判空条件要同时覆盖 fast 与 fast.next，因为快指针一次跳两格，两个位置都可能踩空。

这套结构可迁移到任何「函数迭代找环」的问题：把 x -> next(x) 换成 x -> nums[x] 或 x -> 各位平方和(x) 即可原样复用。

面试视角：先给出哈希集合解法说明思路正确，再指出它 $O(n)$ 空间不满足进阶，然后现场推一遍 a 与 c 的关系式。这道题的分水岭不是能否判环，而是能否讲清楚「为什么从头再走一遍就能落在入环点」。

易错点总结

循环里先判 slow == fast 再推进：任何输入下第一轮都成立，3 → 2 → 0 → -4 会直接返回头节点 3，而正确答案是节点 2。

循环条件只写 fast != null：无环链表 1 → 2 走到 fast = 2 时 fast.next.next 触发空指针异常。

循环条件只写 fast.next != null：无环链表 1 → 2 上 fast 先变成 null，再取 fast.next 同样空指针。

相遇后又多推进了一次快指针再开始比较：3 → 2 → 0 → -4 的相遇点被错认成 2，第二段返回节点 0，答案偏移一位。

用节点值判等：链表 1 → 1 → 1 且尾指向第二个 1 时，slow.val == fast.val 在第一轮就成立，返回错误节点。

第二段循环忘记推进 slow：写成 while (answer != slow) answer = answer.next;，slow 原地不动，answer 撞上的是相遇点而不是入环点；若 answer 走的直尾巴上根本没有该节点还会一直绕环不停。

无环时返回 head 而不是 null：1 → 2 → 3 会被判成「入环点是 1」，与题意完全相反。

对单节点自环提前特判返回 null：1 → 1 确实有环且入环点是它自己，这个特判会漏掉合法用例。

把访问过的节点 next 指向自身来做标记：题目明确不允许改动链表，判题复用同一份输入时后续用例会全错。

相似题目

题目	难度	考察点
141. 环形链表	简单	只需判断有没有环，写到「相遇即返回 true」就结束，不必推导入环点
142. 环形链表 II	中等	与本题同题，可直接套用两段循环的写法
202. 快乐数	简单	把 `next` 换成「各位平方和」，是否成环等价于数字是否快乐
287. 寻找重复数	中等	把下标视作节点、`nums[i]` 视作 `next`，入环点即重复的那个数
457. 环形数组是否存在循环	中等	环还要求同向且长度大于 1，需额外校验方向并对每个起点重试
面试题 02.08. 环路检测	中等	与本题同题，可直接套用
160. 相交链表	简单	同样求首个公共节点，但靠两条路径等长互换而非速度差