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