LeetCode 142. Linked List Cycle

@(LeetCode)

问题描述

给定一个链表，返回环入口节点。如果不存在环，则返回 null。

为了表示带环链表，将使用整数 pos 来表示环入口位置。如果 pos 为 -1，表示无环。

栗 1：

输入：head = [3,2,0,-4], pos = 1
输出：第二个节点

链表如下图所示：

WX20200213-213032@2x.png

栗 2：

输入：head = [1,2], pos = 0
输出：第一个节点

链表如下图所示：

WX20200213-213041@2x.png

栗 3：

输入：head = [1], pos = -1
输出：null
因为无环。

注意：不要修改链表。

想看英文描述的戳这里。

解题思路

要想求出环的入口节点，首先得判断链表是否有环。

链表是否有环

判断链表是否有环，可以通过快慢指针来实现。因为如果带环，会始终在环里绕圈。此时若速度一快一慢，总可以在某个时间点相遇。

可以换个场景思考。如果有两位同学 A、B，他们从同一起点开始，分别以 va、vb 的速度在操场上不断绕圈走路。其中 va > vb，那么一定存在某个时刻，A 会与 B 相遇。因为 A 比 B 走的快，最终 A 在经历 n 圈后，会遇到 B。

数学公式如下：

// L 为操场周长，n 为绕圈次数
(va - vb) * t = n * L

那么在链表中，我们可以假设快指针一次走两步，慢指针一次走一步，等到他们相遇，即快慢指针指向的节点相同，则说明有环。否则，若其中一个指针为空的时候，则说明无环。

// 快慢指针，p1 一次走一步，p2 一次走两步
let p1 = head
let p2 = head

while (p1 && p2) {

    // 走一步
    if (p1.next) {
        p1 = p1.next
    } else {
        return null
    }

    // 走两步
    if (p2.next && p2.next.next) {
        p2 = p2.next.next
    } else {
        return null
    }

    // 相等，则有环
    if (p1 === p2) {
    }
}

// 无环

环入口节点

求环入口节点，也需要用到数学计算。

假设环的长度为 c，头结点与环入口节点的距离为 a，环入口与相遇节点距离为 b。如下图所示：

WX20200213-223747@2x.png

那么 a + b 为慢指针走的距离，a + b + n * c 为快指针走的距离。它们满足如下公式：

// n 为绕圈次数
(a + b) / v1 = (a + b + n * c) / v2
v2 = 2 * v1

进一步得出：

2 * (a + b) = a + b + n * c
a + b = n * c => (a + b) = (n - 1) * c + c

令 n = 1， 则 a = c - b。c - b 其实是相遇节点到环入口节点的距离（以链表顺序方向来看）。这说明：「头节点与环入口节点的距离」 等于 「相遇节点与环入口节点的距离」。进一步可推断出，若头节点和相遇节点以相同速度移动，那么它们相遇时正好是环入口位置。

因此我们可以用两个指针，一个指向头结点，一个指向相遇节点，以相同速度，一次一步。当指向的节点相等时，则为环入口节点。

// 相等，则有环
if (p1 === p2) {
    // 从头结点和相遇节点开始，一次一步，若相等，则为入口
    let p3 = head
    while (p3 !== p1) {
        p3 = p3.next
        p1 = p1.next
    }

    return p1
}