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 <dc****@moonflare.com> 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).