LeetCode-142 环形链表 II

题目描述

给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

不允许修改 链表。

数据样例

示例 1：

1
2
3
输入：head = [3,2,0,-4], pos = 1
输出：返回索引为 1 的链表节点
解释：链表中有一个环，其尾部连接到第二个节点。

示例 2：

1
2
3
输入：head = [1,2], pos = 0
输出：返回索引为 0 的链表节点
解释：链表中有一个环，其尾部连接到第一个节点。

示例 3：

1
2
3
输入：head = [1], pos = -1
输出：返回 null
解释：链表中没有环。

提示：

  • 链表中节点的数目范围在范围 $[0, 10 ^ 4]$ 内
  • $-10 ^ 5 \leq Node.val \leq 10 ^ 5$
  • pos 的值为 -1 或者链表中的一个有效索引

进阶：你是否可以使用 $O(1)$ 空间解决此题？

快慢指针 - $O(N)$

这个题目快慢指针思路巧妙

快慢指针相遇

  • 使用两个指针（快慢指针）：移动速度快的指针叫做 fast, 慢的指针叫做 slow
    • slow：从起点 head 出发，每次链表方向上移动 $1$ 个位置
    • fast：从起点 head 出发，每次链表方向上移动 $2$ 个位置

快慢指针移动过程如下图所示：

  • 相遇点 和 环入口点 上方距离为 $b$，下方距离为 $c$
  • 快慢指针一定会在环内相遇

相遇时，两个指针的移动距离：

  • 快指针移动距离 $L_f$：假设相遇前快指针在环上移动了 $n$ 圈，之后移动至相遇点。
    $$L_f = a + n * (b + c) + b$$
  • 慢指针移动距离 $L_s$：从环入口点开始移动至相遇点
    $$L_s = a + b$$

寻找环入口点

由于 两个指针经过相同的时间，快指针速度是慢指针速度的两倍，因此 移动的距离也是两倍关系：

$$
L_f = 2 * L_s \Rightarrow a + n * (b + c) + b = 2 * (a + b)
$$

通过计算我们得到关系：

$$
a = (n - 1) * (b + c) + c
$$

快慢指针相遇时发现：

  • 此时 slow 指针在 距离环入口点 $c$ 距离的位置（也就是相遇点位置）
  • 我们额外使用一个指针 ptr，从起点出发，那么此时其 距离环入口点 $a$ 距离的位置（也就是起点位置）

此时，如果 slow, ptr 同时开始 每次均移动 $1$ 个位置

由于 $a = (n - 1) * (b + c) + c$，可以得知：slow, ptr 相遇点就是环入口点

时间复杂度 - $O(N)$

  • 慢指针 slow 会走到相遇点，因此走过的长度不会超过链表总长度：$O(N)$
  • ptr 指针最后会走到环入口点，因此其走过的长度也不会超过链表总长度：$O(N)$

因此整体时间复杂度为：$O(N)$

空间复杂度 - $O(1)$

  • 仅使用了若干个指针

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func detectCycle(head *ListNode) *ListNode {
    // 如果链表为空，则不存在环，返回 nil
    if head == nil { return nil }
    // 最开始快慢指针均从起点出发，因此初始化为 head
    slow, fast := head, head
    // 快慢指针开始移动寻找相遇点：如果快指针移动到链表尾部，则说明不存在环，跳出循环
    for fast != nil {
        // 快慢指针向后均先移动 1 个位置，注意：这里快指针只移动 1 个位置，后面会移动第 2 个位置。目的是：判断是否是移动到链表尾部了。
        // 如果快指针直接移动 2 个位置，则可能快指针后面 1 个位置就到链表尾部了，那么其实是无法移动 2 个位置的，会出错
        slow, fast = slow.Next, fast.Next
        // 如果移动过程中，快指针如果移动到链表尾部了，说明不存在环
        if fast == nil { return nil }
        // 快指针再移动 1 个位置
        fast = fast.Next
        // 如果快慢指针相遇了，则开始寻找环入口点
        if slow == fast {
            // 这里，我们可以直接将 fast 用作 ptr，初始化为 head，也就是从起点出发
            fast = head
            // slow, fast(ptr) 依次移动 1 个位置，直到相遇
            for slow != fast { slow, fast = slow.Next, fast.Next }
            // 相遇点即为环入口点，返回这个位置
            return slow
        }
    }
    // 如果跳出循环，说明链表中不存在环，则返回 nil
    return nil
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        if (!head) return NULL;
        auto slow = head, fast = head;
        while (fast) {
            slow = slow->next, fast = fast->next;
            if (!fast) return NULL;
            fast = fast->next;
            if (slow == fast) {
                fast = head;
                while (slow != fast) slow = slow->next, fast = fast->next;
                return slow;
            }
        }
        return NULL;
    }
};