javascriptperformancedata-structuresecmascript-6singly-linked-list

Why I'm hitting time limit!? LeetCode Linked List Cycle (Solved but explanation needed!)


I'm working on solving LeetCode problem 141. Linked List Cycle:

Given head, the head of a linked list, determine if the linked list has a cycle in it.

There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail's next pointer is connected to. Note that pos is not passed as a parameter.

Return true if there is a cycle in the linked list. Otherwise, return false.

Example 1:

Input: head = [3,2,0,-4], pos = 1
Output: true
Explanation: There is a cycle in the linked list, where the tail connects to the 1st node (0-indexed).

My original solution (Version A) exceeded the time limit on the above input. I was eventually able to make the solution fast enough by changing two lines of code (Version B) and the solution was accepted and somehow more efficient.

Why is Version B faster than Version A? Why is the variable assignment faster/more efficient than using the original object?

I changed this...

Version A (Failing Solution)

/**
 * @param {ListNode} head
 * @return {boolean}
 */
var hasCycle = function(head) {
    // create a fast pointer
    let fastPointer = null;
    // create a while loop that lasts for as long as head exists
    while (head) {
        // move fast pointer over by 2
        fastPointer = head?.next?.next || null;
        // if fastpointer is null, this indicates that there is no cycle so return false
        if (fastPointer === null) return false;
        // compare fastPointer to the slow pointer, if they are ever equal to the same node then the list contains a cycle.
        if (fastPointer === head) return true;
        // move head by 1
        head = head.next;
    }
    // if the while loop ends, it indicates the there is no cycle so return false
    return false;
};   

to this ...

Version B (Working Solution)

var hasCycle = function(head) {
    // create a fast pointer
    let fastPointer = head; // !!!CHANGE #1
    // create a while loop that lasts for as long as head exists
    while (head) {
        // move fast pointer over by 2 
        // !!!CHANGE #2 and solution worked!!!!
        fastPointer = fastPointer?.next?.next || null;
        // if fastpointer is null, this indicates that there is no cycle so return false
        if (fastPointer === null) return false;
        // compare fastPointer to the slow pointer, if they are ever equal to the same node then the list contains a cycle.
        if (fastPointer === head) return true;
        // move head by 1
        head = head.next;
    }
    // if the while loop ends, it indicates the there is no cycle so return false
    return false;
};   

Solution

  • In the faulty version, the loop has fastPointer leading by two nodes compared to head. But that means that fastPointer is not really going faster... it is just ahead two nodes, but going at the same "speed" as head. What you really need is that fastPointer will increase its lead at every step, so that fastPointer is twice as far in the linked list compared to head, not just 2 nodes ahead.

    This also explains why the first version hits the time limit: it will get into an infinite loop when the input list has a cycle, and that cycle has a size different from 2. In that case fastPointer will never become equal to head, since it is exactly 2 nodes away from head. For instance, if the cycle has 3 nodes, then fastPointer will be 2 nodes ahead of head, and eventually (once arrived in the cycle) also one node behind head. This never changes: this distance will remain the same and so the loop never ends.