CODEWITHSUNDEEP
algorithm
Hommer Smith
Hommer Smith

Reputation: 27852

Hare and tortoise algorithm. Why is the collision spot and head of linked list at the same distance of the start of the loop?

In the Cracking the Coding interview book, it is given the following explanation about the how to find where the beginning of a loop is in a linked list:

There is a FastRunner which advances two steps, and a SlowRunner which advances two steps (per unit of time).

k -> number of nodes before loop K = mod(k, LOOP_SIZE) -> number of steps the fast runner is inside the loop when the slow runner just hit the first node in the loop.

FastRunner is LOOP_SIZE - K steps behind SlowRunner FastRunner catches up to SLowRunner at a rate of 1 step per unit of time.

They meet after LOOP_SIZE - K, at this point they will be K steps before the head of the loop.

In order to find the start of the loop, the author says that: Since K = mod(k, LOOP_SIZE), we can say that k = K + M * LOOP_SIZE (for any integer M), then here is where I get lost, she says that it is correct to say that it is k nodes from the loop start.

I understand that the collision point is K nodes from the loop start, but why it is also k nodes? How does she finds that K = k?

Upvotes: 0

Views: 306

Answers (1)

Mateusz Dymczyk
Mateusz Dymczyk

Reputation: 15141

Well K is the number of nodes inside the loop the faster one "jumped" through until the slower one entered the loop. The faster one goes 2x faster than the slower one, so the faster one had to jump through 2*k nodes in total (because it takes k for the slower one to get to the loop). So the number of jumps it did in the loop is K=2*k-k (all jumps minus jumps it made to get to the loop) so K == k

Upvotes: 3

Related Questions