skip to Main Content

I’m working on solving this problem on leetcode (https://leetcode.com/problems/linked-list-cycle/description/) and my original solution exceeded the time limit (Example A). I was eventually able to make the solution fast enough by changing two lines of code and the solution was accepted and some how more performant. Why is example B faster than example A? Why is the variable assignment faster/more performant than using the original object?

I changed this…

Example A (Failing Solution)

var hasCycle = function(head) {
// some code ...
   let fastPointer = null;

   fastPointer = head?.next?.next || null;
// ...
}

to this …

Example B (Working Solution)

var hasCycle = function(head) {
// some code ...
   let fastPointer = head;

   fastPointer = fastPointer?.next?.next || null;
// ...
}

Here is the full code for both solutions…

Example 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;
};   

Example B (Working Solution)…

/**
 * @param {ListNode} head
 * @return {boolean}
 */
var hasCycle = function(head) {
   // create a fast pointer
   let fastPointer = head;

   // create a while loop that lasts for as long as head exists

   while (head) {
    // move fast pointer over by 2 
    // !!!CHANGE HAPPENED HERE 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;
};   

2

Answers


  1. in the first solution you define

    let fastPointer = null;
    

    and then you make this:

    fastPointer = fastPointer?.next?.next || null;
    

    that means you are trying to re assign the variable and the variable is already null this mean

    fastPointer = null?.next?.next || null;
    

    in the first Optional chaining it’s already null
    that mean this condition:

    if (fastPointer === null)
    

    is true and will return false even though I have a cycle and the code will not complete execution

    so basically this is not time exceeds "this is returning false right away…

    Login or Signup to reply.
  2. 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.

    Login or Signup to reply.
Please signup or login to give your own answer.
Back To Top
Search