@rahul, instead of head2=head2->next->next; u cn put -- head2= (head2 -> next) ? (head2->next->next) : head2 -> next;
this will take care of situation wen head2->next is null. On Wed, Aug 31, 2011 at 1:02 PM, sukran dhawan <[email protected]>wrote: > use hair and tortoise rule to find loop > find the number of nodes in a loop by keeping one poiner and moving the > other > > then use two pointers and one pointer at the head and list and oher ptr n > nodes away frm pointer 1 where n is the length is the loop > > > while(second ptr ->next != first pointer) > > //travese and increment counter > > ..done :) > > On Wed, Aug 31, 2011 at 8:19 PM, Don <[email protected]> wrote: > >> @Ravi: >> Count the nodes in the loop. >> Step one point that many nodes into the list. >> Start another pointer at the head. >> Step both pointers until the two "next" pointers are equal. >> Now you have the two nodes which have the same "next" pointer. >> >> Don >> >> >> // Returns NULL if there is no loop >> // Returns pointer to last node before the loop if there is a loop >> Node *FindLoop(Node *head) >> { >> Node *p1=head, *p2=head; >> while(p2) >> { >> p2 = p2->next; >> if (p2) p2 = p2->next; >> p1 = p1->next; >> if (p1 == p2) break; >> } >> if (!p2) return 0; >> >> // Count nodes in loop >> int count = 1; >> for(p2=p1->next; p2 != p1; p2 = p2->next) >> ++count; >> >> // Start p1 at head and p2 at position count >> p1 = p2 = head; >> for(int i = 0; i < count; ++i) >> p2 = p2->next; >> >> // Find entrance point to loop >> while(p1->next != p2->next) >> { >> p1 = p1->next; >> p2 = p2->next; >> } >> >> return p1; >> } >> >> >> On Aug 31, 8:18 am, ravi maggon <[email protected]> wrote: >> > In one of my interview at winshuttle I was asked the same ques but their >> was >> > an addon to this. Find the point where the loop occurs. >> > For eg: >> > 1->2->3->4->5->6->7->8->9->5 >> > >> > so output should be 5 >> > >> > can anyone give the algo for this. >> > >> > On Wed, Aug 31, 2011 at 6:44 PM, Piyush Grover < >> [email protected]>wrote: >> > >> > >> > >> > > This is fine but adding a twist to it. >> > > Find number of nodes which are not in the loop. >> > >> > > On Wed, Aug 31, 2011 at 6:27 PM, rahul sharma < >> [email protected]>wrote: >> > >> > >> int loop(void *head1,void *head2) >> > >> { >> > >> //head1 and head2 initialized to start; >> > >> while(head1!=NULL && head2!=NULL) >> > >> { >> > >> head1=head1->next; >> > >> head2=head2->next->next; >> > >> if(head1==head2) >> > >> return 1;////tehre is loop; >> > >> } >> > >> return 0;//no loop >> > >> } >> > >> > >> hi guys is it corect for finding the loop...if any test case that >> wont >> > >> works here plz tell... >> > >> > >> -- >> > >> You received this message because you are subscribed to the Google >> Groups >> > >> "Algorithm Geeks" group. >> > >> To post to this group, send email to [email protected]. >> > >> To unsubscribe from this group, send email to >> > >> [email protected]. >> > >> 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 [email protected]. >> > > To unsubscribe from this group, send email to >> > > [email protected]. >> > > For more options, visit this group at >> > >http://groups.google.com/group/algogeeks?hl=en. >> > >> > -- >> > >> > Regards >> > Ravi Maggon >> > Final Year, B.E. CSE >> > Thapar University >> >> -- >> You received this message because you are subscribed to the Google Groups >> "Algorithm Geeks" group. >> To post to this group, send email to [email protected]. >> To unsubscribe from this group, send email to >> [email protected]. >> 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 [email protected]. > To unsubscribe from this group, send email to > [email protected]. > 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 [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
