142. Linked List Cycle II

原题地址：142. Linked List Cycle II

解法一

1
2
3
4
5
6
7
8
9
10
11
12
13
//brute force，很容易想到
var detectCycle = function(head) {
    const set = new Set();
    while(head) {
        if(set.has(head)) {
            return head;
        }
        set.add(head);
        head = head.next;
    }

    return null;
};

解法二

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
var detectCycle = function(head) {
    let slow = head;
    let fast = head;
    while (slow && fast && fast.next) {
        slow = slow.next;
        fast = fast.next.next;
        
        if (slow === fast) { //这里有些难理解
            while (head !== fast) {
                head = head.next;
                fast = fast.next;
            }
            return head;
        }
    }
    return null;
};

这个解法用的还是 Linked List Cycle里面的快慢双指针的思路。

外层循环通过快慢指针判断是否有环，内层循环找出环的起始点。

下面用一幅图解释下为什么内层循环这样做可以找到环的起始点：
pic
假设链表起点到环起点距离为x1，环起点到快慢指针相遇节点距离为x3，环的长度为2*x2。

快慢指针相遇时慢指针走的距离是：

1
slowDistance = x1 + x2

快指针有的距离是：

1
fastDistance = x1 + x3 + 2 * x2

由于快指针移动速度是慢指针两倍：

1
fastDistance = 2 * slowDistance

由上可得：

1
x1 = 2 * x2 - x3

x1是链表起点到环起点的距离，2 * x2 - x3是快指针绕回环起点的距离。因此只要以相同速度移动链表起点和快指针，它们第一次一定会在环起点相遇。