473,326 Members | 2,133 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,326 software developers and data experts.

removing a loop from a linked list?

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;
}
Nov 14 '05 #1
5 11430
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.
Nov 14 '05 #2
Jani Yusef <ja**@persian.com> 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.
Nov 14 '05 #3
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).
Nov 14 '05 #4
ja**@persian.com (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 );
}

Nov 14 '05 #5
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
Nov 14 '05 #6

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

13
by: na1paj | last post by:
here's a simple linked list program. the DeleteNode function is producing an infinit loop i think, but i can't figure out where.. #include <stdio.h> typedef struct { char *str; //str is a...
7
by: ssantamariagarcia | last post by:
I have found a problem while using a while statement and a linked list. I had never met this matter before....and I am wondering that if you have , please tell me what it is wrong. I am...
10
by: sonu | last post by:
Hi All, here i have a daught how can i find wheather a linked list contains a loop or not.
3
by: blubzouf | last post by:
I am searching some info about accessing files with stdio functions. I am able to open a file, read in it with freaf, write in it with fwrite, modifying its data in "r+" mode ( without truncation...
5
by: nuffnough | last post by:
This is python 2.4.3 on WinXP under PythonWin. I have a config file with many blank lines and many other lines that I don't need. read the file in, splitlines to make a list, then run a loop...
3
by: rameshwar83 | last post by:
Suppose we have a linked list..... haviing loop..... suggest me some algo to remove loop from list..... Ex. A->B->C->D->E->F->G->H->I->E in this list node iI points to node E .... make...
2
by: Rohit kumar Chandel | last post by:
How to find whether there is a loop in a linked list. suppose I have a linked list in the shape of numeral 9(next pointer of last node points to somewhere in the middle of list instead of pointing...
7
by: =?Utf-8?B?Sm9lbCBNZXJr?= | last post by:
I have created a custom class with both value type members and reference type members. I then have another custom class which inherits from a generic list of my first class. This custom listneeds...
2
by: sathishc58 | last post by:
Hi Can anyone explain me the difference between circular linked list and looped linked list? 1) In Circular linked list Next part of last node will be pointing to the first nodes starting...
0
by: ryjfgjl | last post by:
ExcelToDatabase: batch import excel into database automatically...
1
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
0
by: Vimpel783 | last post by:
Hello! Guys, I found this code on the Internet, but I need to modify it a little. It works well, the problem is this: Data is sent from only one cell, in this case B5, but it is necessary that data...
0
by: ArrayDB | last post by:
The error message I've encountered is; ERROR:root:Error generating model response: exception: access violation writing 0x0000000000005140, which seems to be indicative of an access violation...
1
by: PapaRatzi | last post by:
Hello, I am teaching myself MS Access forms design and Visual Basic. I've created a table to capture a list of Top 30 singles and forms to capture new entries. The final step is a form (unbound)...
1
by: CloudSolutions | last post by:
Introduction: For many beginners and individual users, requiring a credit card and email registration may pose a barrier when starting to use cloud servers. However, some cloud server providers now...
1
by: Defcon1945 | last post by:
I'm trying to learn Python using Pycharm but import shutil doesn't work
1
by: Shællîpôpï 09 | last post by:
If u are using a keypad phone, how do u turn on JavaScript, to access features like WhatsApp, Facebook, Instagram....
0
by: Faith0G | last post by:
I am starting a new it consulting business and it's been a while since I setup a new website. Is wordpress still the best web based software for hosting a 5 page website? The webpages will be...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.