142. Linked List Cycle II

Leetcode link

题目简介

/**
 * @param {ListNode} head
 * @return {ListNode}
 */

本题是 141 题的进阶版本，题目给我们一个链表头 head

要求我们找出链表中回路开始的节点，如果链表不存在回路则返回 null

解题思路

这题的解法分为两步：

1. 通过快慢指针找到令指针相遇的节点
2. 从 head 与相遇节点同时出发，直到两个指针相遇，相遇的节点就是回路开始的节点

为什么呢？

对于每一个带回路的链表，我们可以把它们拆分成三个部分：

• A：从 head 到回路开始节点的部分
• B：从回路开始节点到快慢指针相遇节点的部分
• C：从快慢指针相遇节点到回路开始节点的部分

我们快慢指针的特点是，快指针前进速度是慢指针两倍

于是有了如下公式：

经过整理得：

于是我们得到了：从 head 到回路开始节点的部分 = 从快慢指针相遇节点到回路开始节点的部分

Javascript

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var detectCycle = function (head) {
    // step 1: we find a cycle
    let slow = head
    let fast = head

    while (fast && fast.next) {
        slow = slow.next
        fast = fast.next.next
        if (slow === fast) {
            // step 2: Moving from head and fast, the node where they meet is the target node
            slow = head
            while (slow !== fast) {
                slow = slow.next
                fast = fast.next
            }
            return fast
        }
    }
    return null
};