Given a circular linked list, implement an algorithm which returns the node at the beginning of the loop.
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
0
of 0 votes
Thanks for your response, I can understand that when the slow runner is k step behind fast runner and when they finally meet the slow runner is k steps away from home.
But I am still struggling to understand why "If you go counterclockwise from SlowRunner to FastRunner, it would be LOOPSIZE-K."
and why they always meet at exactly "LOOPSIZE-K"
They define "K" (capital K) to be the amount of nodes in the loop from the point when the slow runner hits the head. Since FastRunner is twice as fast, it obviously gets in the loop before slow runner does. At the point in time when slow runner is ABOUT to take its first step into the loop, FastRunner is already K steps in.
- Anonymous October 01, 2014Since the loop has a finite size in this question, it is fair to say that FastRunner is the "size of the loop minus K" steps BEHIND the slow runner (assuming it were to go all the way around again.) After all, a loop is like a circle. If you go clockwise into the loop, Slow runner is K behind FastRunner. If you go counterclockwise from SlowRunner to FastRunner, it would be LOOPSIZE-K.
FastRunner moves twice as fast as SlowRunner (Fast = 2 steps at a time, Slow = 1 step). Thus FastRunner moves 1 more step closer to SlowRunner every time. Once they finally meet, they will be K steps away from the start of the loop. (Keep in mind, K also represented the distance from the start to the entry of the loop.)
Therefore you can reset SlowRunner, and move both SlowRunner and FastRunner by 1 step each time. When they meet (after K steps), they will have collided a second time at the node that starts the loop.