loop in a linked linked lists

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?

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..

---

http://www.daniweb.com/techtalkforum...ad.php?t=46403

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..

Depending on what the struct that makes up the linked list looks like you might be able to do something like:

Code:

---

NODE *n;

for(n = list_head;n;n = n->next)
{
  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.

That's what I just said ;)

Quote:

---

Originally Posted by itsme86

That's what I just said ;)

---

Too much time previewing and reading Dave's link.

>You might need to wrap all the nodes in a dummy struct that contains the node and that flag member.
U r essentially talking about nesting the node structure with a suitable wrapper structure that defines the "flag" parameter right?
Yeah, this gives a better time complexity too just O(n)..