Two Pointers travelling at a different speed has to meet and this is the
reason . Say the length of the loop is X. If we move both the pointers X
times the fast moving pointer would have moved 2X location and the other
one has moved only X locations. So 2X Pointer proceeds in advance over the
others.
So when the 2X Pointer moves in front of the other there is only 2
possibilities
1) They meet at a location. (Hence they meet)
2) They were in adjacent location, in which case in the next
iteration they will meet. ( Hence they have to meet compulsorily)
Second step is just algebra and assume m is the number of steps on which
they meet
so you have to solve the equation (k+2m) modulo n = m modulo n.
Thanks,
Arun.
On Sat, Mar 17, 2012 at 7:19 AM, rahul sharma <rahul23111...@gmail.com>wrote:
> i earlier post same question and got the satifactory response from dave
> ..but now i got new explanation from carcking the coding interview..
>
> plz explain this with example........thnx in advance,
>
> If we move two pointers, one with speed 1 and another with speed 2, they
> will end up meeting if the linked list has a loop. Why? Think about two
> cars driving on a track—the faster car will always pass the slower one!
> The tricky part here is finding the start of the loop. Imagine, as an
> analogy, two people racing around a track, one running twice as fast as the
> other. If they start off at the same place, when will they next meet? They
> will next meet at the start of the next lap.
> Now, let’s suppose Fast Runner had a head start of k meters on an n step
> lap. When will they next meet? They will meet k meters before the start of
> the next lap. (Why? Fast Runner would have made k + 2(n - k) steps,
> including its head start, and Slow Runner would have made n - k steps. Both
> will be k steps before the start of the loop.)
> Now, going back to the problem, when Fast Runner (n2) and Slow Runner (n1)
> are moving around our circular linked list, n2 will have a head start on
> the loop when n1 enters. Specifically, it will have a head start of k,
> where k is the number of nodes before the loop. Since n2 has a head start
> of k nodes, n1 and n2 will meet k nodes before the start of the loop.
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
