removing a loop from a linked list?

[Jani Yusef]

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;
}

 

[Derrick Coetzee]

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.

 

[Christopher Benson-Manica]

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.

 

[Francois Grieu]

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.

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

 

[Tim Rentsch]

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 );
}

 

[pete]

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.