Grokking the Coding Interview: Patterns for Coding Questions
Vote

0% completed

​

Solution: LinkedList Cycle

.....

.....

.....

Like the course? Get enrolled and start learning!
A

Anonymous

· 3 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
A

Anonymous

· 5 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

Reading Progress

0%

Vote for new content