LeetCode LCR 022. 环形链表 II

约 4 分钟
文章信息 5 个分类 4 个标签
分类
LeetCode 中等 119 经典题变种挑战 剑指 Offer 剑指 Offer（专项突击版）
标签
哈希表 双指针 LCR 链表

题目描述

✅ LCR 022. 环形链表 II

image-20260928235002618

image-20260928235002619

题意分析

判断单链表是否有环；若有环，返回从头节点出发第一次进入环的那个节点，没有环则返回空。入口是节点对象，不是它的值，值相同不表示指向同一节点。

不能修改节点之间的连接。链表可能为空，也可能单节点自环，或者头节点本身就是入口。需要进一步用常数额外空间完成，不能依赖集合保存全部访问历史。

解法：快慢指针判环并找入口

核心思路

[!blue]

先用两个指针判断有无环。slow 每轮走一步，fast 每轮走两步，均从头出发。没有环时快指针会到达空；有环时两者进入环后，相对位置每轮改变一格，最多再经过一个环长就会重合。

必须先移动再比较，因为初始时它们本来就指向同一个头节点，这不能作为有环的依据。快指针移动前同时检查自己和后继，保证一次走两步合法。

为什么相遇后能找到入口？设头到入口距离为 a，环长为 L，相遇时慢指针共走了 t 步。快指针走了 2t 步，两者位于同一个环内节点，路程差 t 必须是环长的整数倍，即 t % L == 0。

相遇点相对入口的环内偏移是 (t - a) % L。从相遇点再走 a 步，偏移变成 t % L = 0，恰好回到入口。同时从头出发的另一个指针走 a 步，也第一次到达入口。因此将一个指针放回头，另一个留在相遇点，让它们都每轮走一步即可。

在走满 a 步之前，从头出发的指针仍在非环前缀，另一指针始终在环内，不会提前相遇；头本身就是入口时，两者在第二阶段开始时已经相等。这一推导允许慢指针绕过整圈，不必假设第一次相遇前它只走了头到入口再到相遇点的最短距离。

解题步骤

  1. 将快慢指针都初始化为 head。
  2. 只要 fast 和 fast.next 都非空，慢指针走一步、快指针走两步。
  3. 移动后比较节点引用；若相遇，令 answer = head，保留慢指针的位置。
  4. answer 与慢指针同步走一步，第一次引用相等时返回该节点。
  5. 第一阶段先走到链尾则返回空，表示无环。

代码实现

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

        while (fast != null && fast.next != null) {
            // 先推进再判等，避免同起点在第一轮被误判为相遇。
            slow = slow.next;
            fast = fast.next.next;

            if (slow == fast) {
                // 相遇时慢指针总步数是环长整数倍，从头与相遇点同速走到入口。
                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 {
            // 相遇时慢指针总步数是环长整数倍，从头与相遇点同速走到入口。
            answer := head
            for answer != slow {
                answer = answer.Next
                slow = slow.Next
            }
            return answer
        }
    }
    return nil
}

复杂度分析

  • 时间复杂度：$O(n)$，其中 $n$ 是可达的不同节点数。第一阶段进入环后至多再走一个环长相遇，第二阶段走头到入口的距离。
  • 空间复杂度：$O(1)$，只使用固定数量的指针，不修改链表。

关键点总结

[!green]

  • 快慢速度差保证有环时相遇，快指针到空则说明无环。
  • 相遇时慢指针总路程是环长整数倍，这是入口定位的关键关系。
  • 头与相遇点同步再走头到入口的距离，都落在入口。
  • 两个阶段均按节点身份比较，不能比较节点值。

易错点总结

[!yellow]

  • 初始指针相等不能判环，第一阶段必须先走再比较。
  • 只检查 fast 而不检查 fast.next，无法保证两步跳转安全。
  • 第二阶段两个指针都走一步，不能继续沿用两倍速度。
  • 路程推导要允许完整绕圈，不能把实际总步数一律当成最短路程。
  • 用修改 next 的方式标记访问，会破坏题目要求保留的链表结构。

相似题目

题目 难度 关联与区别
141. 环形链表 简单 先用快慢指针判断有环，本题还要根据相遇位置推导并寻找入环点。
287. 寻找重复数 中等 把数组下标跳转视为函数图，可复用找环入口的方法确定重复值。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/71579853
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！