CODEWITHSUNDEEP
algorithmdata-structureslinked-listgraph-theory
bragboy
bragboy

Reputation: 35572

Cycle detection in a linked list : Exhaustive theory

This is NOT the problem about detecting cycle in a linked list using the famous Hare and Tortoise method.

In the Hare & Tortoise method we have pointers running in 1x and 2x speeds to determine that they meet and I am convinced that its the most efficient way and the order of that type of search is O(n).

The problem is I have to come up with a proof (proving or disproving) that it is possible that two pointers will always meet when the moving speed is Ax (A times x) and Bx (B times x) and A is not equal to B. Where A an B are two random integers operating on a linked list with a cycle present.

This was asked in one of interviews I recently attended and I was not able to prove it comprehensively to myself that whether the above is possible. Any help appreciated.

Upvotes: 8

Views: 1022

Answers (3)

PengOne
PengOne

Reputation: 48398

Suppose there is a loop, say of length L.

Easy case first

To make it easier, first consider the case where the two particles entire loop at the same time. These particles are at the same position whenever n*A = n*B (mod L) for some positive integer n, which is the number of steps until they meet again. Taking n=L gives one solution (though there may be a smaller solution). So after L units of time, particle A has made A trips around the loop to be back at the beginning and particle B has made B trips around the loop to be back at the beginning, where they happily collide.

General Case

Now what happens when they do not enter the loop at the same time? Let A be the slower particle, i.e. A<B, and suppose A enters the loop at time m, and let's call the position at which A enters the loop 0 (since they're in the loop, they can never leave it, so I'm just renaming positions by subtracting A*m, the distance A has traveled after m time units). Then, at that time, B is already at position m*(B-A) (it's real position after m time units is B*m and it's renamed position is therefore B*m-A*m). Then we need to show that there is a time n such that n*A = n*B+m*(B-A) (mod L). That is, we need a solution to the modular equation

(n+m) * (A-B) = 0 (mod L)

Taking n = k*L-m for k large enough that k*L>m does the trick, though again, there may be a smaller solution.

Therefore, yes, they always meet.

Upvotes: 10

n. m. could be an AI
n. m. could be an AI

Reputation: 120079

The hypothesis is false. For instance, if both pointers make leaps of an even size, the loop is also of even size, and distance between the pointers is odd, they will never meet.

UPD this is apparently an impossible situation. Because the two pointers start at the same point, the distance between them will always be even.

Upvotes: -1

user97370
user97370

Reputation:

If your two step-sizes have a common factor x: let's say the step sizes are Ax and Bx, then just consider the sequence you get from taking the original sequence and taking every x'th element. This new sequence has a cycle if and only if the original sequence does, and taking steps of size A and B on it is equivalent to taking steps of size Ax and Bx on the original sequence.

This reduction means that it's sufficient to prove that the algorithm works when A and B are coprime.

Upvotes: 1

Related Questions