@ 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 <[email protected]> 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 <[email protected]> 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 [email protected].
>> To unsubscribe from this group, send email to
>> [email protected]<algogeeks%[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]<algogeeks%[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.
