当前位置：首页 > news >正文

【LeetCode 热题 100】142. 环形链表 II——快慢指针

news 2025/7/12 19:37:38

Problem: 142. 环形链表 II
题目：给定一个链表的头节点 head ，返回链表开始入环的第一个节点。如果链表无环，则返回 null。

文章目录

整体思路
完整代码
时空复杂度
- 时间复杂度：O(N)
- 空间复杂度：O(1)

整体思路

这段代码旨在解决一个比“判断环形链表”更进阶的问题：环形链表 II (Linked List Cycle II)。问题不仅要求判断链表中是否存在环，还要求找到环的入口节点。如果不存在环，则返回 null。

该算法同样基于 Floyd判圈算法（快慢指针），但它巧妙地增加了第二阶段的查找，以精确定位环的入口。

第一阶段：判断是否有环并找到相遇点
- 这部分与 hasCycle 问题的逻辑完全相同。
- 使用一个 slow 指针（每次走一步）和一个 fast 指针（每次走两步），从 head 出发。
- 如果链表有环，它们最终会在环内的某个点相遇。
- 如果 fast 或 fast.next 变为 null，说明无环，直接返回 null。
第二阶段：从相遇点找到环的入口
- 这是算法最精妙的部分，基于一个重要的数学推导：
  - 设链表头到环入口的距离为 a。
  - 设环的长度为 b。
  - 设环入口到快慢指针相遇点的距离为 x。
  - 当快慢指针相遇时：
    - 慢指针走过的距离是 s = a + x。
    - 快指针走过的距离是 f = a + n*b + x (快指针可能在环里绕了n圈)。
  - 由于快指针速度是慢指针的两倍，所以 f = 2s。
  - 代入得：a + n*b + x = 2(a + x)。
  - 化简得：a + x = n*b。
  - 进一步变形得到：a = n*b - x。这个公式还可以写成 a = (n-1)*b + (b-x)。
- 核心结论：a = (n-1)*b + (b-x) 这个公式告诉我们一个惊人的事实：
  - 从链表头 (head) 到环入口的距离 a，
  - 等于
  - 从相遇点 (slow/fast) 沿环前进到环入口的距离 b-x，再加上 n-1 圈环的长度。
- 利用结论：这意味着，如果我们现在设置两个指针，一个从 head 出发，另一个从相遇点 slow 出发，它们都以相同的速度（每次一步）前进，那么它们必然会在环的入口处相遇。
算法实现步骤：
- 完成第一阶段后，如果 slow == fast，说明找到了相遇点。
- 此时，保持 slow 指针在相遇点不动，将另一个指针（这里复用了 head 指针）重新置于链表的头部。
- 启动第二个 while 循环，让 head 和 slow 指针同步前进（每次一步）。
- 当 head == slow 时，它们相遇的位置就是环的入口节点。返回 slow（或 head）。

完整代码

/*** Definition for singly-linked list.* class ListNode {*     int val;*     ListNode next;*     ListNode(int x) {*         val = x;*         next = null;*     }* }*/
public class Solution {/*** 找到环形链表的入口节点。* @param head 链表的头节点* @return 环的入口节点，如果无环则返回 null*/public ListNode detectCycle(ListNode head) {// 初始化快慢指针ListNode slow = head;ListNode fast = head;// 步骤 1: 判断是否有环，并找到相遇点while (fast != null && fast.next != null) {slow = slow.next;       // 慢指针走一步fast = fast.next.next;  // 快指针走两步// 如果相遇，说明有环if (slow == fast) {// 步骤 2: 从相遇点找到环的入口// 将一个指针（这里复用 head）重新置于链表头部// 另一个指针（slow）保持在相遇点// 两个指针以相同的速度前进，相遇点即为环的入口while (head != slow) {head = head.next;slow = slow.next;}// 返回环的入口节点return slow;}}// 如果循环结束，说明快指针到达链表末尾，不存在环return null;}
}

时空复杂度

时间复杂度：O(N)

第一阶段（找相遇点）：如 hasCycle 问题分析，这部分的时间复杂度是 O(N)。
第二阶段（找环入口）：
- head 指针从头开始走，直到环入口，走了 a 步。
- slow 指针从相遇点开始走，直到环入口，也走了 a 步。
- 由于 a < N，这部分的时间复杂度也是 O(N)。