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'snext
pointer is connected to. Note thatpos
is not passed as a parameter.Return
true
if there is a cycle in the linked list. Otherwise, returnfalse
.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...
/**
* @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 ...
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;
};
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.