leetcode-go/medium/142.js

'use strict'

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

function ListNode(val) {
    this.val = val
    this.next = null
}

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var detectCycle = function (head) {
    // Assume l1 = dis(head, entry), and l2 = dis(entry, meeting),
    // c = len(cycle), n = count of loop (fast pointer), then
    // dis(head, fast) = l1+l2+n*c = 2*dis(head, slow) = 2*(l1+l2).
    // So l1 = c-l2+(n-1)*c, for a pointer in cycle, it means
    // l1 = c - l2, ie. dis(head, entry) = dis(meeting, entry).
    if (!head) return null
    let slow = head
    let fast = head
    let entry = head
    while (fast.next && fast.next.next) {
        slow = slow.next
        fast = fast.next.next
        if (fast === slow) {
            while (entry !== slow) {
                entry = entry.next
                slow = slow.next
            }
            return entry
        }
    }
    return null
}

function __main__() {
    /* eslint no-console: ["error", {"allow": ["log"]}] */
    const logger = console.log.bind(console)
    const n5 = new ListNode(5)
    const n4 = new ListNode(4)
    n4.next = n5
    const n3 = new ListNode(3)
    n3.next = n4
    const n2 = new ListNode(2)
    n2.next = n3 
    const n1 = new ListNode(1)
    n1.next = n2
    n5.next = n3
    logger(n3)
    logger(detectCycle(n1))
}

__main__()