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