142. 环形链表 II

[devinxiang]

描述

解题：

/**
 * 参考：https://leetcode-cn.com/problems/linked-list-cycle-ii/solution/huan-xing-lian-biao-ii-by-leetcode-solution/ 题解
 * 继续深入，如何寻找到入环的节点。两个节点同时从起点开始走
 * 1. 快针走的是慢针的两倍。
 * 2. 因为慢针走过的路，快针已经走过一遍；
 * 3. 快针走过的剩余路程，也就是和慢针走过的全部路程相等。(a+b = c+b)
 * 4. 刨去快针追赶慢针的半圈(b)，剩余路程即为所求入环距离(a=c)
 * 所以当他们相遇的时候，这时候，这时候声明一个新的指针从 head 开始走，当它和慢指针相遇的时候，就是他们相遇的节点。
 */
var detectCycle = function (head) {
    if (head === null) return null;
    let slow = head;
    let fast = head;

    while (fast !== null) {
        slow = slow.next;
        if (fast.next !== null) {
            fast = fast.next.next;
        } else {
            return null;
        }

        if (fast === slow) {
            let ptr = head;
            while (ptr !== slow) {
                ptr = ptr.next;
                slow = slow.next;
            }
            return ptr;
        }
    }

    return null;
}