@ snehal I have a doubt. Are you sure this will terminate and find the looping node?
>slow1=head; > while( slow1!=slow) >{ >prev=slow; >slow=slow->next; >slow1=slow1->next; >} Consider this example list with nodes 1-12 looping node 5. 1 > 2 > 3 > 4 > 5 > 6 > 7 > 8 - | | 12 < 11 < 10 < 9 Initially slow is at 6 and slow1 is at 1 after 7moves slow comes at 5 while slow1 at 8 (they don't meet so far). Now will the above code will slow and slow1 ever meet once both of them are traversing the loop with single moves? May be I am not getting this correctly please explain if I havent understood it fully? On Thu, Jan 13, 2011 at 5:20 PM, snehal jain <learner....@gmail.com> wrote: > @ above > > your code is only detecting loop.. my code is detecting loop and then > removing loop as well > > > On Thu, Jan 13, 2011 at 5:04 PM, bittu <shashank7andr...@gmail.com> wrote: > >> @snehal ..although ur approach ir good but u make d problem little >> complex,also missed out little checking, it can be done by using 2 >> pointers & single while loop--Now Instruction(CPU) Matters. >> >> Rather then presenting different-2 algorithm i will present very >> famous algorithm Floyd’s Cycle-Finding Algorithm: >> >> it is the fastest method. Traverse linked list using two pointers. >> Move one pointer by one and other pointer by two. If these pointers >> meet at some node then there is a loop. If pointers do not meet then >> linked list doesn’t have loop. >> >> Time complexity O(n) >> Space Complexity O(1) >> >> >> Code-Snippet Below >> >> int is_loop(struct node *list) >> { >> struct node *slow_p = list, *fast_p = list; >> >> while(slow_p && fast_p && >> slow_p->next && >> fast_p->next && >> fast_p->next->next ) >> { >> slow_p = slow_p->next; >> fast_p = fast_p->next->next; >> if (slow_p == fast_p) >> { >> printf("Found Loop"); >> return 1; >> } >> } >> return 0; >> } >> >> >> It Will Surely Works. >> >> >> Regards >> Shashank Mani "Don't b Evil U Can Learn whilw U Earn" >> >> -- >> 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<algogeeks%2bunsubscr...@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<algogeeks%2bunsubscr...@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.