removing a loop from a linked list?

Discussion in 'C Programming' started by Jani Yusef, Sep 20, 2004.

  1. Jani Yusef

    Jani Yusef Guest

    Based on an interview question I heard of but did not know the answer
    to.......
    How do you find and remove a loop from a singly linked list?
    In a google groups search I found the following code which will detect
    the loop but I am stumped how one would remove this loop.
    Any ideas?


    typedef enum { FALSE, TRUE } bool;

    /* The empty list is represented by NULL. */
    typedef struct sList {
    void *car;
    struct sList *cdr;
    } *List;

    /* Have two pointers into the list (l and m). Advance m twice as
    fast as l; if they ever point to the same place then the list
    has a loop in it. */
    bool iterativeSolution (List *l) {
    List *m = l;
    while (m) {
    l = l->cdr;
    if (m && (m = m->cdr) && (m = m->cdr) && l == m)
    return TRUE;
    }
    return FALSE;
    }
    Jani Yusef, Sep 20, 2004
    #1
    1. Advertising

  2. Jani Yusef wrote:
    > How do you find and remove a loop from a singly linked list?
    > In a google groups search I found the following code which will detect
    > the loop but I am stumped how one would remove this loop.


    If it's a loop of linked list *nodes*, you probably don't want to
    actually remove the entire loop with all its nodes. You can cause the
    list to not have a loop and still have the same elements, however, by
    truncating the list (setting next to a null pointer) right before it
    begins to loop. Accomplishing this would require you track the previous
    node as you're looking for duplicates, so that you can assign its next
    pointer when you find a duplicate to cut the loop.

    If you have a loop of *values*, this is a different matter - in this
    case just assign the next pointer of the first occurence to the next
    pointer of the second occurence, and repeat until the list is full of
    unique values. This probably isn't what they meant, though.
    --
    Derrick Coetzee
    I grant this newsgroup posting into the public domain. I disclaim all
    express or implied warranty and all liability. I am not a professional.
    Derrick Coetzee, Sep 21, 2004
    #2
    1. Advertising

  3. Jani Yusef <> spoke thus:

    > Based on an interview question I heard of but did not know the answer
    > to.......
    > How do you find and remove a loop from a singly linked list?
    > In a google groups search I found the following code which will detect
    > the loop but I am stumped how one would remove this loop.


    In a strange twist of fate, I just asked a very similar question in
    comp.programming. You may find the replies to that post helpful.

    --
    Christopher Benson-Manica | I *should* know what I'm talking about - if I
    ataru(at)cyberspace.org | don't, I need to know. Flames welcome.
    Christopher Benson-Manica, Sep 21, 2004
    #3
  4. OP gave:

    typedef enum { FALSE, TRUE } bool;

    /* The empty list is represented by NULL. */
    typedef struct sList {
    void *car;
    struct sList *cdr;
    } *List;

    /* Have two pointers into the list (l and m). Advance m twice as
    fast as l; if they ever point to the same place then the list
    has a loop in it. */
    bool iterativeSolution (List *l) {
    List *m = l;
    while (m) {
    l = l->cdr;
    if (m && (m = m->cdr) && (m = m->cdr) && l == m)
    return TRUE;
    }
    return FALSE;
    }

    and asked "how one would remove this loop" in the linked list,
    once it is found there is one.


    Derrick Coetzee <> wrote:

    > If it's a loop of linked list *nodes*, you probably don't want to
    > actually remove the entire loop with all its nodes. You can cause the
    > list to not have a loop and still have the same elements, however, by
    > truncating the list (setting next to a null pointer) right before it
    > begins to loop. Accomplishing this would require you track the previous
    > node as you're looking for duplicates, so that you can assign its next
    > pointer when you find a duplicate to cut the loop.


    Problem is, the OP's code does not locate where the loop closes.

    Partial spoiler follows.
    ..
    ..
    ..
    ..
    ..
    ..
    ..
    ..
    ..
    ..
    ..
    ..
    ..
    ..
    ..
    ..
    Count the number of steps that the algorithm makes when it
    return TRUE. Then step again to find the cycle length. Deduce how
    many steps need to be further made before reaching where the loop
    closes.

    Which brings us to an on-topic question: what built-in ISO C type(s)
    can portably be used as counter for this purpose ?


    Francois Grieu


    Side note:
    if (m && (m = m->cdr) && (m = m->cdr) && l == m)
    can be simplified to
    if ((m = m->cdr) && (m = m->cdr) && l == m)
    and that even then there remains one redeundant test
    in the loop (that an optimizing compiler might catch).
    Francois Grieu, Sep 21, 2004
    #4
  5. Jani Yusef

    Tim Rentsch Guest

    (Jani Yusef) writes:

    > Based on an interview question I heard of but did not know the answer
    > to.......
    > How do you find and remove a loop from a singly linked list?
    > In a google groups search I found the following code which will detect
    > the loop but I am stumped how one would remove this loop.
    > Any ideas?


    Step 1 - find an element 'b' that is part of the loop.

    Step 2 - starting at the beginning of the list, step along
    it, setting to zero any pointer that is part of
    the loop and that points to the element in question.

    The resulting algorithm is N squared in the length of the
    list, but uses no marking bits or extra memory.


    The code:


    typedef struct ListElement_struct {
    void *head; /* or car, if you prefer */
    struct ListElement_struct *next; /* or cdr, if you prefer */
    } *List;


    static void
    break_loop( List possibly_looped ){
    List list = possibly_looped, a = list, b = list;

    do {
    if( b == 0 || b->next == 0 ) return;

    a = a->next, b = b->next->next;
    } while( a != b );

    while( list ){
    a = b;
    do {
    if( a->next == list ){
    a->next = 0;
    return;
    }

    } while( a = a->next, a != b );

    list = list->next;
    }

    ASSERT( FALSE );
    }
    Tim Rentsch, Sep 21, 2004
    #5
  6. Jani Yusef

    pete Guest

    Francois Grieu wrote:

    > Count the number of steps that the algorithm makes when it
    > return TRUE. Then step again to find the cycle length. Deduce how
    > many steps need to be further made before reaching where the loop
    > closes.
    >
    > Which brings us to an on-topic question: what built-in ISO C type(s)
    > can portably be used as counter for this purpose ?


    I was thinking that it should be either
    the longest unsigned type, or size_t.
    I believe that malloc is allowed allocate
    more than SIZE_MAX list nodes.

    The longest unsigned type in C89 is long unsigned.
    I decided to go with size_t.
    size_t has the potential to be the longest unsigned type,
    in both C89 and C99, though it is not guaranteed to be
    the longest unsigned type in either.

    --
    pete
    pete, Sep 21, 2004
    #6
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Chris Ritchey
    Replies:
    7
    Views:
    463
    emerth
    Jul 10, 2003
  2. fool
    Replies:
    14
    Views:
    491
    Barry Schwarz
    Jul 3, 2006
  3. joshd
    Replies:
    12
    Views:
    654
    John Carson
    Oct 2, 2006
  4. mac
    Replies:
    1
    Views:
    1,460
    Jens Thoms Toerring
    May 27, 2008
  5. Isaac Won
    Replies:
    9
    Views:
    349
    Ulrich Eckhardt
    Mar 4, 2013
Loading...

Share This Page