Leetcode——142. Linked List Cycle II

刷题时看到这道题，看了解答觉得很数学&有趣，就来写个数学证明题吧hhhh

题目

Given a linked list, return the node where the cycle begins. If there is no cycle, return null.

Leetcode链接

分析

其实这是Linked List Cycle的升级版，和1一样，首先判断是否成环，采用快慢指针的方法，这里就不多加解释。

当我们确定是成环时，我们需要去寻找环的头部。

解法一：map记录

这是一个最简单的方法就是用map记录环中的点，然后从头开始找第一个在map中的点，这里我也就不放代码了。

时间复杂度$O(n)$，但空间复杂度有点高。。

解法二：双指针寻找(数学原理）

这是我想记录的一个方法，个人认为没见过解答一般没法想出来，倒是可能猜到？

做法：假设前面快慢指针分别为a和b，现在a和b应指向同一个节点，只需选择其中一个（如a）与一个新的指向头部head的节点的指针c一起往前走，它们第一次指向的同一个节点就是环的第一个节点。

简单来说写个伪代码：

// a is a previous pointer
c = head;
while (a != c) {
  a = a->next;
  c = c->next;
}

是不是很神奇？完全想不到啊

时间复杂度$O(n)$，空间复杂度$O(1)$。

证明

首先，定义这里的长度为需要走的步数。

假设从head到环的头部的长度为$S_{head}$，环的长度为$S_{circle}$。
在前面的算法，慢指针a走了$S_a$，快指针b走了$S_b$。
则我们有
$$S_b = 2 * S_a$$

又因为现在a和b在同一个点，因此b比a多走$k$圈，即
$$S_b - S_a = k * S_{circle}$$
$$S_a = k * S_{circle}$$

那么若a又走了$S_1$的长度的话（即从头走到环头部的长度）
$$S_a’ = S_{head} + S_a$$
$$S_a’ = S_{head} + k * S_{circle}$$

这就正好是走了一个头部到环的距离+$k$圈环，也就是a正好在环的头部。

代码

ListNode *detectCycle(ListNode *head) {
    if (head == NULL) return NULL;
    ListNode *a = head;
    ListNode *b = head;
    while (a != NULL && b != NULL && b->next != NULL) {
        a = a->next;
        b = b->next->next;
        if (a == b) break;
    }
    if (b == NULL || b->next == NULL)
        return NULL;

    b = head;
    while (a != b) {
        a = a->next;
        b = b->next;
    }
    return a;
}