Linked List Detection: A Comprehensive Theory

Question

This is NOT a problem with loop detection in a linked list using the well-known Hare and Tortoise method.

In the Hare and Turtle method, we have pointers working at 1x and 2x speeds to determine that they occur, and I am convinced that O (n) is the most efficient way and order of this type of search.

The problem is that I have to come up with a proof (to prove or disprove) that it is possible that two pointers will always meet when the speed is Ax (A times x) and Bx (B times x) and A is not equal to B. Where A a B are two random integers working in a linked list with a loop present.

This was asked in an interview that I recently visited, and I could not fully tell about myself whether it is possible above. Any help was appreciated.

Answer 1

Suppose that there exists a cycle, for example, length L

Simple case one

To make it easier, we first consider the case when a whole loop of two particles at the same time. These particles are in the same position when n*A = n*B (mod L) for some positive integer n , which is the number of steps until they are assembled again. Taking n=L gives one solution (although there may be a smaller solution). Thus, after L units of time, particle A made A fires around the cycle to return at the beginning, and particle B made B fires around the cycle to return at the beginning, where they happily collide.

General case

Now, what happens when they do not enter the cycle at the same time? Let A be a slower particle, i.e. A<B , and let A enter the loop at time m and can call the position where A enters loop 0 (since they are in the loop, they can never leave it, so I just rename the positions by subtracting A*m , distance A passed through m units of time). Then at this time B already in position m*(BA) (this is the real position after m units of time B*m , and therefore it is renamed to position B*mA*m ). Then we need to show that there exists a time n such that n*A = n*B+m*(BA) (mod L) . That is, we need a solution to the modular equation

 (n+m) * (AB) = 0 (mod L) 

Taking n = k*Lm for k large enough for k*L>m do the trick, although again there may be a smaller solution.

Therefore, yes, they always meet.

Answer 2

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

This reduction means that it is enough to prove that the algorithm works when A and B are coprime.

Answer 3

The hypothesis is false. For example, if both pointers make jumps of even size, the cycle also has an even size, and the distance between the pointers is odd, they will never meet.

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