Take the 2-minute tour ×

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.

share|improve this question

3 Answers 3

up vote 10 down vote accepted

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.

share|improve this answer

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.

share|improve this answer
You also know however that they start on the same point at the beginning. If you consider Paul Hankin argument it should be clear that your case is not possible (if there is any prime factor in common between A and B then you can get to an equivalent case in which this factor has been removed). –  6502 Dec 17 '11 at 8:40
"You also know however that they start on the same point at the beginning" — they do not necessarily enter the loop at the same time as there is an initial non-loopy portion of the list. –  n.m. Dec 17 '11 at 8:48
Oh, I see it's not possible indeed. –  n.m. Dec 17 '11 at 8:53

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.

share|improve this answer
"This new sequence has a cycle if and only if the original sequence does" — this is false. –  n.m. Dec 17 '11 at 8:38
@n.m.: Uh? for a linked list the property of looping back is not changed if you step over it every x items. Either you keep stepping forever for both cases (there is a cycle) or you stop after n or n/x steps (there is no cycle). Of course the cycle length is not going to be necessarely k/x if the original cycle is of length k... but this is irrelevant to the argument. –  6502 Dec 17 '11 at 8:48
Sorry I was wrong. This is not false. I misunderstood the statement. –  n.m. Dec 17 '11 at 9:26

Your Answer


