Thread: loop in a linked linked lists

  1. #1
    Eager young mind
    Join Date
    Jun 2006
    Posts
    342

    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?
    In the middle of difficulty, lies opportunity

  2. #2
    Just Lurking Dave_Sinkula's Avatar
    Join Date
    Oct 2002
    Posts
    5,005
    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
    7. It is easier to write an incorrect program than understand a correct one.
    40. There are two ways to write error-free programs; only the third one works.*

  3. #3
    Eager young mind
    Join Date
    Jun 2006
    Posts
    342
    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..
    In the middle of difficulty, lies opportunity

  4. #4
    Gawking at stupidity
    Join Date
    Jul 2004
    Location
    Oregon, USA
    Posts
    3,218
    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.
    If you understand what you're doing, you're not learning anything.

  5. #5
    Gawking at stupidity
    Join Date
    Jul 2004
    Location
    Oregon, USA
    Posts
    3,218
    That's what I just said
    If you understand what you're doing, you're not learning anything.

  6. #6
    Registered User
    Join Date
    Oct 2004
    Posts
    151
    Quote Originally Posted by itsme86
    That's what I just said
    Too much time previewing and reading Dave's link.
    System: Debian Sid and FreeBSD 7.0. Both with GCC 4.3.

    Useful resources:
    comp.lang.c FAQ | C++ FQA Lite

  7. #7
    Eager young mind
    Join Date
    Jun 2006
    Posts
    342
    >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)..
    In the middle of difficulty, lies opportunity

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Doubly linked lists
    By mohanlon in forum C Programming
    Replies: 8
    Last Post: 12-08-2010, 01:01 AM
  2. need help understanding Linked lists
    By Brain Cell in forum C Programming
    Replies: 6
    Last Post: 07-16-2004, 01:29 PM
  3. Freeing Linked Lists
    By mrpickle in forum C Programming
    Replies: 4
    Last Post: 01-21-2004, 07:57 PM
  4. Linked Lists
    By xddxogm3 in forum C++ Programming
    Replies: 3
    Last Post: 09-25-2003, 03:14 PM
  5. One more question about linked lists?
    By shaeng in forum C Programming
    Replies: 2
    Last Post: 06-24-2003, 07:36 AM