A very popular problem is finding whether a linked list has a loop. The solution basically uses two pointers, one at normal pace and one at 2x pace. Let us assume two people are running a race. The race starts from a starting point, say my home. Then, both runners reach a park and do some laps around the park. Slow guy - S and Fast Guy - F. Fast guy goes at twice the speed of slow guy, reaches the park and keeps doing laps when finally both slow and fast guy meet at some point. Let us try to model this mathematically. When the slow guy enters the park, assume he would have covered C nodes. The faster guy, F, would have done 2*C. Let us now add another variable k, which is the distance of F from the loop start. And another variable, the loop size, let us call it n. Now, let us imagine when both runners meet. By the time S covers half a loop(n/2), F covers n and has a headstart of k, so he would have covered n + k. By the time S covers a distance of n - k, F covers a distance of 2*( n - k). Given the headstart of F, he would be at 2*(n - k) +k = 2*n - k. Since n is a circular loop, this translates to position n - k. So, both S and F meet at n - k.
Now, Let us send F back to the start and ask him to do this slowly while we keep S walking at normal pace. When F would have covered C (yeah! our first variable from the start to the mouth of the loop), S would have walked C too. Now, going back to some interesting stuff about C. When S covered C, F covered 2*C. that means from the mouth of the loop, it have moved C nodes. That means C = b*n + k. so, when F covers C he will be at the mouth of the loop, but when S covers C from our earlier meeting position, that is n - k, he would have covered: n - k + b*n +k = (b+1)*n, i.e. he too would be at the mouth of the loop.
This took me some real time to understand, so I am adding pictures to help.
No comments:
Post a Comment