• 08-26-2006
kris.c
I have access to fast internet only for this weekend, so let me clear all my doubts..

I have a singly linked list with unique satellite data in each node.. Its given that there is a possibility of a loop in it..
The first part of the question is to check if there is a loop or not..
The next part is to find out where the loop actually starts..

For the first part, we can use "fast pointer - slow pointer " method and its pretty trivial..For the second part.. I could think of an algorithm which is O(n*2)
wherein,

one pointer p : is pointing to the head of the ll,
another pointer q : is pointing to the node where the fast and the slow pointers met in the first part..

In each iteration :
p moved to the next node ,
q is made to go around the loop till it returns to the point where it started,
chaeck if p an q point to the same node .. If they do, then that is the point where the loop starts, else continue

This is too inefficient.. Can some one suggest a better algo?
• 08-26-2006
Dave_Sinkula
Quote:

Originally Posted by kris.c
I have a singly linked list with unique satellite data in each node.. Its given that there is a possibility of a loop in it..

• 08-26-2006
kris.c
hey Dave, that link tells me something that i already know.. It does not specify the algo to find out where the loop starts.. Did i miss anything? sorry if i did..
• 08-26-2006
itsme86
Depending on what the struct that makes up the linked list looks like you might be able to do something like:
Code:

NODE *n;

{
if(n->flag) // some dummy flag that doesn't disrupt the data in the node.
{
printf("Start of loop at address: %p\n", n);
break;
}

n->flag = 1;
}

Then just run through your struct again and clear the flag if needed. At most, you'll need to run through the linked list twice.

But like I said, that depends on whether or not the nodes make a dummy flag feasible. You might need to wrap all the nodes in a dummy struct that contains the node and that flag member.
• 08-26-2006
itsme86
That's what I just said ;)
• 08-26-2006
zx-1
Quote:

Originally Posted by itsme86
That's what I just said ;)