Grokking the Coding Interview: Patterns for Coding Questions

0% completed

​

Solution: LinkedList Cycle

Problem Statement

Given the head of a Singly LinkedList, write a function to determine if the LinkedList has a cycle in it or not.

Constraints:

  • The number of the nodes in the list is in the range [0, 10<sup>4</sup>].
  • -10<sup>5</sup> <= Node.val <= 10<sup>5</sup>

Solution

Imagine two racers running in a circular racing track. If one racer is faster than the other, the faster racer is bound to catch up and cross the slower racer from behind. We can use this fact to devise an algorithm to determine if a LinkedList has a cycle in it or not.

.....

.....

.....

Like the course? Get enrolled and start learning!
H

hj3yoo

· 4 years ago

For the similar question, I don't think we need to iterate through the cycle again.

The fast pointer travels twice as fast as the slow pointer, and it has covered the same distance that the slow pointer has covered plus an entire cycle. Mathematically, this means that: 2 * d_slow = d_slow + d_cycle, which simplifies to d_cycle = d_slow.

Therefore, we can keep track of how many nodes the slow pointers travelled until the fast pointer meets it and return that value.

Haven't tested in code, but please correct me if I'm wrong.

Show 5 replies
Faraz Ahmed

Faraz Ahmed

· 2 years ago

iam confused how the fast (object) will be equal to slow(object), coz in javascript two object are never same they have different memory addressess!

1,2,3,4,5,6

in this list, the fast pointer reaches the end, and the fast===slow is not being satisfied,i get it but will fast === slow will be evaluated to true ? if we are comparing two objects?

Show 1 reply
Denys Stopkin

Denys Stopkin

· a year ago

Why doesn't it have a loop? [1,2,3,4,5,6]

6 The last node loops itself as far as I get from the explanation. Only this->next == nullptr in the last node means there's no loop in the list