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
in the first solution you define
and then you make this:
that means you are trying to re assign the variable and the variable is already null this mean
in the first Optional chaining it’s already null
that mean this condition:
is true and will return false even though I have a cycle and the code will not complete execution
In the faulty version, the loop has
fastPointer
leading by two nodes compared tohead
. But that means thatfastPointer
is not really going faster… it is just ahead two nodes, but going at the same "speed" ashead
. What you really need is thatfastPointer
will increase its lead at every step, so thatfastPointer
is twice as far in the linked list compared tohead
, 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 tohead
, since it is exactly 2 nodes away fromhead
. For instance, if the cycle has 3 nodes, thenfastPointer
will be 2 nodes ahead ofhead
, and eventually (once arrived in the cycle) also one node behindhead
. This never changes: this distance will remain the same and so the loop never ends.