itz ryt...loop starts from 4 n not from 5... On Fri, Mar 9, 2012 at 8:58 PM, sanjiv yadav <sanjiv2009...@gmail.com>wrote:
> I think u r making mistake i.e. after 7,5 will com not 4 because loop > starts from 5.check it again > > On 3/9/12, rahul sharma <rahul23111...@gmail.com> wrote: > > @sanjiv.......how can u take q at c.????they will meet at some position > ... > > suppose u have > > > > 1-2-3-4-5-6-7-4 > > > > now initialy > > > > slow and fast both at 1 > > start incrementing slow by 1 and fast by 2 > > > > slow @2 ...fast @3 > > slow @3....fast @5 > > s...@4...fast@7 > > slow @5...fast@5 > > > > both are equal....means dere is loop. > > > > take anyone of the slow/fast say fast @ start i.e @1 > > > > now we have s...@5...fast@1... > > incrementing bith by 1 > > > > s...@6...fast@2 > > s...@7....fast@3 > > s...@4..fast@4... > > they are equal..means we are at start of loop..... > > > > i got the algo...but didnt get the logic....how they are meeting @start. > > > > > > On Fri, Mar 9, 2012 at 7:42 PM, sanjiv yadav <sanjiv2009...@gmail.com > >wrote: > > > >> suppose linked list is > >> > >> a->b->c->d->e > >> > >> and suppose loop starts from 'c' > >> > >> according to u let one pointer be at 'c' say *q and another be at 'a' > say > >> *p. Now if we move both at the speed of one then > >> > >> After first pass > >> > >> p will be at b > >> > >> q will be at d > >> > >> After second pass > >> > >> p will be at c > >> > >> q will be at e > >> > >> After third pass > >> > >> p will be at d > >> > >> q will be at c > >> > >> After fourth pass > >> > >> p will be at e > >> > >> q will be at d > >> > >> After fifth pass > >> > >> p will be at c > >> > >> q will be at e > >> > >> > >> and so on. > >> > >> Correct me if i am wrong. > >> > >> > >> On Fri, Mar 9, 2012 at 7:28 PM, rahul sharma > >> <rahul23111...@gmail.com>wrote: > >> > >>> @terence....i cant get..can u eleborate....thnx for the sol..but plz > >>> elaborate... > >>> > >>> > >>> On Fri, Mar 9, 2012 at 5:59 PM, Terence <technic....@gmail.com> wrote: > >>> > >>>> @ rahul sharma: > >>>> the linked list is a combination of a list a->b->...->p->q and a cycle > >>>> q->r->...->z->q. (z != p). > >>>> noting that the start of cycle q is the only node with 2 predecessor: > p > >>>> and z. > >>>> if 2 pointers meet at some node x, different from q, in last step they > >>>> must have met at x', the predecessor of x. > >>>> the above logic holds for all nodes in cycle except q. > >>>> > >>>> @ sanjiv yadav: > >>>> They will meet at the start of loop. > >>>> ex. a->b->c->d->e->c->d->e... > >>>> First round: > >>>> A: a->b->c->d > >>>> B: a->c->e->d > >>>> meet at d. > >>>> Second round: > >>>> A: a->b->c > >>>> B: d->e->c > >>>> meet at c. > >>>> > >>>> > >>>> On 2012-3-9 18:39, sanjiv yadav wrote: > >>>> > >>>> No They will not meet at the start in a case containing 5 nods and > >>>> having loop at the third node. once check this > >>>> > >>>> On Fri, Mar 9, 2012 at 3:48 PM, rahul sharma > >>>> <rahul23111...@gmail.com>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 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. > >>>> > >>>> -- > >>>> 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. > >>> > >> > >> > >> > >> -- > >> 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. > >> > > > > -- > > 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. > > > > > > > -- > 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. > > -- 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.