题解 | #链表中环的入口结点#JS 版解法 - 快慢指针法

JavaScript 版解法

function EntryNodeOfLoop(pHead) {
    let fast = pHead, slow = pHead;
    while (fast != null && fast.next != null) {
        // 快、慢指针每次分别走两步、一步
        fast = fast.next.next;
        slow = slow.next;
        if (fast === slow) break;  // 如果二者相遇就退出循环
    }
    // 判断快指针是否已经到达链表尾部，如果是，那说明链表无环，返回 null
    if (fast == null || fast.next == null) return null;
    slow = pHead;  // 如果有环，令慢指针重新指向头节点，快指针仍指向相遇点
    // 这一次，快慢指针每次都走一步，二者相遇点即为链表环的入口节点
    while (fast != slow) {
        fast = fast.next;
        slow = slow.next;
    }
    return fast;
}

至于为什么“第二次，快慢指针每次都走一步，二者一定会相遇且首次相遇点即为链表环的入口节点”，读者可参考 详解为什么用一步两步快慢指针？三步四步可以吗 。