actually how u r moving from 7 to 4????? can tell me in the detail...............
On Sat, Mar 10, 2012 at 4:37 AM, Dave <dave_and_da...@juno.com> wrote: > @Rahul: The definitions of m and p are in the first sentence of the > posting. > > Dave > > On Friday, March 9, 2012 12:46:43 PM UTC-6, rahul sharma wrote: > >> @dave.. >> >> plz tell use of variable...m and p?? >> p i thnik no. of nodes in cycle..??? >> >> plz tell what is p and m???? >> >> On Fri, Mar 9, 2012 at 10:16 PM, Dave <dave_and_da...@juno.com> wrote: >> >>> @Rahul: You have to figure out where the fast and slow pointers meet, >>> which will depend on the distance m from the head to the cycle and the >>> period p of the cycle. It is awkward to explain in words, so draw a picture >>> and label it according to this discussion. >>> >>> Suppose the two pointers meet k nodes from the beginning of the cycle. >>> Then the slow pointer has moved m + t*p + k nodes, where t is the number of >>> times the slow pointer traverses the cycle, and the fast pointer has moved >>> m + u*p + k nodes, where u is the number of times the fast pointer has >>> traversed the cycle. The number of double steps of the fast pointer is (m + >>> u*p +k)/2, and this equals the number of single steps the slow pointer has >>> taken. Thus, m + u*p + k = 2(m + t*p + k), so k = (2*t - u)*p - m, i.e., >>> some number of times around the cycle minus m. Now start the fast pointer >>> at the head and take m single steps with both pointers. The fast pointer is >>> at the beginning of the cycle, and the slow pointer has traversed the cycle >>> (2*t - u) times and is back at the beginning of the cycle. The pointers >>> couldn't be equal sooner since the fast pointer is not in the cycle after >>> less than m steps and the slow pointer is in the cycle. >>> >>> Dave >>> >>> On Friday, March 9, 2012 4:18:14 AM UTC-6, rahul sharma wrote: >>> >>>> i have 2 pointers fast and slow.....now if tehy meet there is a loop... >>>> >>>> now keep one ptr at meeting point and take other one to the begining of >>>> list....move both at speed of one..they will meet at start of loop....how >>>> this happens???why they meet at start..plz tell logic behind this???thnx in >>>> advance >>>> >>> -- >>> You received this message because you are subscribed to the Google >>> Groups "Algorithm Geeks" group. >>> To view this discussion on the web visit https://groups.google.com/d/** >>> msg/algogeeks/-/Z0xNjVOTEgkJ<https://groups.google.com/d/msg/algogeeks/-/Z0xNjVOTEgkJ> >>> . >>> >>> To post to this group, send email to algogeeks@googlegroups.com. >>> To unsubscribe from this group, send email to algogeeks+unsubscribe@** >>> googlegroups.com <algogeeks%2bunsubscr...@googlegroups.com>. >>> For more options, visit this group at http://groups.google.com/** >>> group/algogeeks?hl=en <http://groups.google.com/group/algogeeks?hl=en>. >>> >> >> -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To view this discussion on the web visit > https://groups.google.com/d/msg/algogeeks/-/U4Wzxa0ntosJ. > > 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. > -- Regards.... Sanjiv Yadav MobNo.- 8050142693 Email Id- sanjiv2009...@gmail.com -- 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.
