I understand that Tortoise and Hare's meeting concludes the existence of loop, but how does moving tortoise to beginning of linked list while keeping the hare at meeting place, followed by moving both one step at a time make them meet at starting point of cycle?
A:
This is Floyd's algorithm for cycle detection. You are asking about the second phase of the algorithm -- once you've found a node that's part of a cycle, how does one find the start of the cycle?
In the first part of Floyd's algorithm, the hare moves two steps for every step of the tortoise. If the tortoise and hare ever meet, there is a cycle, and the meeting point is part of the cycle, but not necessarily the first node in the cycle.
When the tortoise and hare meet, we have found the smallest i (the number of steps taken by the tortoise) such that Xi = X2i. Let mu represent the number of steps to get from X0 to the start of the cycle, and let lambda represent the length of the cycle. Then i = mu + a*lambda, and 2i = mu + b*lambda, where a and b are integers denoting how many times the tortoise and hare went around the cycle. Subtracting the first equation from the second gives i = (b-a)*lambda, so i is an integer multiple of lambda. Therefore, Xi + mu = Xmu. Xi represents the meeting point of the tortoise and hare. If you move the tortoise back to the starting node X0, and let the tortoise and hare continue at the same speed, after mu additional steps the tortoise will have reached Xmu, and the hare will have reached Xi + mu = Xmu, so the second meeting point denotes the start of the cycle.
Jim Lewis
2010-05-29 19:37:57
@Jim lewis The meeting point will not be a starting point of course, but as I said shifting one of those two to beginning of linked list and moving both at same speed will make them meet at the starting point of cycle.
Passionate programmer
2010-05-29 19:45:18
Check out this page http://en.wikipedia.org/wiki/Cycle_detection
Passionate programmer
2010-05-29 19:56:37
@Passionate: Hope this edit clarifies the situation. The key insight is that the number of (tortoise) steps to the first meeting must be a multiple of the cycle length, and that mu steps from either this position or the start position will take you to the start of the cycle.
Jim Lewis
2010-05-29 22:01:02
@Jim Lewis It would be great if you could explain about how having i as multiple of loop length results to mu as distance between first meeting point and loop beginning.
Passionate programmer
2010-05-30 09:44:10
@Passionate: Take mu steps from the start point to get to `X_mu`, the start of the cycle (by definition of mu). Then if you take i more steps, where i is a multiple of the cycle length, you end up back at the cycle start: `X_mu + i` = `X_mu`. But addition is commutative, so this is equivalent to taking i steps to get from the start to the first meeting point `X_i`, then mu additional steps to get back to `X_mu`, the start of the cycle.
Jim Lewis
2010-05-30 10:02:38
@Jim thanks :).
Passionate programmer
2010-05-30 10:37:32