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.
