PiggyBlog
Published on

LeetCode-142. 环形链表II

Authors

声明：该文通过我个人写Prompt喂给AI产出

问题描述

给定一个链表 list，判断链表中是否存在环。如果存在环，返回环的起始节点；否则返回 null。

原题链接：https://leetcode.cn/problems/linked-list-cycle-ii/

快慢指针法

通过快慢指针找到链表中是否存在环，并进一步找到环的起始节点。

具体思路

  1. 找到快慢指针相遇的位置：

    • slow 指针每次移动一步。
    • fast 指针每次移动两步。
    • 这样快指针总会追到慢指针的，从而能找到快慢指针的相遇的位置。

  2. 快慢指针的相遇之后的处理逻辑：

    • 假设链表头到环的起点的距离为 a。

    • 环的起点到相遇点的距离为 b。

    • 从相遇点再到环的起点的距离为 c。

    • 环的总长度为 L = b + c。

    • 当 slow 和 fast 第一次相遇时：

      • slow 指针走过的距离为 a + b。
      • fast 指针走过的距离为 a + b + k * L，其中 k 是 fast 指针在环中多走的圈数（k ≥ 1）。

    • 因为 fast 的速度是 slow 的两倍，所以：

      2(a + b) = a + b + kL

      化简得到：

      a + b = kL

      进一步可以写成：

      a = kL - b

  3. 找到环的起始节点：

    • 将 slow 指针重新指向链表头节点，fast 指针保持在相遇点。
    • slow 和 fast 同时每次移动 1 步。
    • 当 slow 移动 a 步到达环的起点时，fast 也会移动 a 步。
    • 由于 a = kL - b，fast 指针从相遇点移动 a 步后，相当于移动了 kL - b 步。
    • 因为环的长度是 L，**所以 fast 指针移动 kL 步后会回到原位置，再减去 b 步，**最终会到达环的起点。
    • 因此，slow 和 fast 会在环的起点相遇。

代码实现

以下是快慢指针法的代码实现：

public ListNode detectCycle(ListNode list) {
    if (list == null || list.next == null) {
        return null;
    }
    ListNode slow = list;
    ListNode fast = list;

    // 找到快慢指针的相遇点
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        if (fast == slow) {
            break;
        }
    }
    // 如果没有环，返回 null
    if (fast == null || fast.next == null) {
        return null;
    }
    // 找到环的起始节点
    slow = list;
    while (slow != fast) {
        slow = slow.next;
        fast = fast.next;
    }
    return slow;
}

复杂度分析

  • 时间复杂度：O(n)，其中 n 是链表的长度。
    • 找到快慢指针的相遇点需要 O(n) 的时间。
    • 找到环的起始节点需要 O(n) 的时间。
  • 空间复杂度：O(1)，只使用了常数级别的额外空间。
View on GitHub