linked list...

[Shraddha]

How can I find a loop in a single linked list?
I thought about keeping a flag or traversing list more than once...but
it will require another data structure to store all these things...
Also if the list is having many nodes then this won't ork..
So is there a full proof solution?

 

[Naresh Rautela]

How can I find a loop in a single linked list?
I thought about keeping a flag or traversing list more than once...but
it will require another data structure to store all these things...
Also if the list is having many nodes then this won't ork..
So is there a full proof solution?

Try the Hare and Tortoise approach. Basically have 2 ptrs both
pointing to the start of the list. Increment one pointer by 1 and
another by 2. After each increment comapre if they are equal. If
there is a loop the pointers would meet.

 

[James Kanze]

How can I find a loop in a single linked list?
I thought about keeping a flag or traversing list more than once...but
it will require another data structure to store all these things...
Also if the list is having many nodes then this won't ork..

If you can modify the nodes in the list, you can add a flag,
visited, which is initialized false. Loop, setting the flag
true, until you find the end of the list, or a node with the
flag true. If you encountered the end of the list, there's no
cycle, loop again resetting the flag false (for the next time).
If you encountered a node with the flag true, there's a cycle.
To reset the flags, loop from the beginning, until you encounter
a node with the flag reset.

If you can't modify the nodes in the list, you'll need some sort
of look-aside cache with the addresses of the nodes already
visited; if the list is long, this could require a lot of extra
memory.

 

[Pete Becker]

If you can modify the nodes in the list, you can add a flag,
visited, which is initialized false. Loop, setting the flag
true, until you find the end of the list, or a node with the
flag true. If you encountered the end of the list, there's no
cycle, loop again resetting the flag false (for the next time).
If you encountered a node with the flag true, there's a cycle.
To reset the flags, loop from the beginning, until you encounter
a node with the flag reset.

You don't need to go through the loop a second time if you also keep a
flag telling you the state that you left visited nodes in the last time.
Before starting the main loop you toggle that flag's value, then go
through nodes checking whether the node's flag is equal to the outer
flag; if so, you've got a loop; if not, set the node's flag equal to the
outer flag.

--

-- Pete
Roundhouse Consulting, Ltd. (www.versatilecoding.com)
Author of "The Standard C++ Library Extensions: a Tutorial and
Reference." (www.petebecker.com/tr1book)

 

[dasjotre]

Try the Hare and Tortoise approach. Basically have 2 ptrs both
pointing to the start of the list. Increment one pointer by 1 and
another by 2. After each increment comapre if they are equal. If
there is a loop the pointers would meet.

let me see if I understand this.

so if I have a list

1 1 3

p1 -> 1
p2 -> 1

first increment
p1 = p1+1
p2 = p2+2
p1 -> 1
p2 -> 3
p1 != p2

and ... well you missed the loop.

I guess you meant something like
(assuming there are begin, end and there is ++
operator that does something like p=p->next)

for(p1 = start; p1 != end; ++p1)
{
p2 = p1;
++p2
for(; p2 != end; ++p2)
if(p1 == p2)
! there is a loop !
}

not very efficient.

regards

DS

 

[JT]

Try the Hare and Tortoise approach. Basically have 2 ptrs both
pointing to the start of thelist. Increment one pointer by 1 and
another by 2. After each increment comapre if they are equal. If
there is a loop the pointers would meet.

let me see if I understand this.
so if I have alist
1 1 3

That's not a loop. That's a repeated element,
not a repeated node.

A loop in a singly linked list is necessarily
an infinite loop.

I guess you meant something like
for(p1 = start; p1 != end; ++p1)
{
p2 = p1;
++p2
for(; p2 != end; ++p2)
if(p1 == p2)
! there is a loop !

}

No, the classic technique is this:

p1=start;
p2=start;
while(p1!=NULL && p2!=NULL) {
if (p1==p2)
return "there is a (infinite) loop";
p1=p1+1;
p2=p2+2;
}
return "there is no loop";

If the linked list has no loop, then it is
doing a traversal all the way to the end,
which is O(n), and no worse than doing a element lookup.

If the linked list has a loop, then p1 and p2
will eventually meet (since no matter where the
loop starts, the length before the loop,
and the length inside the loop is always either odd,
or even. And so either p1 and p2 meet during the first
pass thru the loop, or during the second loop.
So it is O(2n), which is O(n) also.

- JT

 

[JT]

the classic technique is this:

p1=start;
p2=start;
while(p1!=NULL && p2!=NULL) {
if (p1==p2)
return "there is a (infinite) loop";
p1=p1+1;
p2=p2+2;
}
return "there is no loop";

My use of "+" in my pseudocode is misleading.
Instead, this is the real code:

class node {
int element;
node* next;
}

....

node *p1=start;
node *p2=start;
while(p1!=NULL && p2!=NULL) {
if (p1==p2)
return true; // Infinite loop found!
p1=p1->next;
p2=p2->next;
if (p2!=NULL) p2=p2->next;
}
return false; // No loop

 

[JT]

node *p1=start;
node *p2=start;
while(p1!=NULL && p2!=NULL) {
if (p1==p2)
return true; // Infinite loop found!
p1=p1->next;
p2=p2->next;
if (p2!=NULL) p2=p2->next;
}
return false; // No loop

Argg!!! I have egg on my face.



I don't have my copy of the algorithm book with me,
so I'm writing from memory. But there is a clear off-by-one
error in my code.

Let me try the 3rd time: (But surely, you get
the idea by now. Whether my quick code has bug
is irrelevant to whether this is a powerful classic technique)

if (start==NULL)
return false; // No loop, obviously
node *p1=start;
node *p2=start->next;
while(p1!=NULL && p2!=NULL) {
if (p1==p2)
return true; // Infinite loop found!
p1=p1->next;
p2=p2->next;
if (p2!=NULL) p2=p2->next;
}
return false; // No loop

 

[=?ISO-8859-1?Q?Erik_Wikstr=F6m?=]

Try the Hare and Tortoise approach. Basically have 2 ptrs both
pointing to the start of the list. Increment one pointer by 1 and
another by 2. After each increment comapre if they are equal. If
there is a loop the pointers would meet.

What is it that I am missing here, wouldn't the simplest approach be to
store a pointer p1 to the "beginning" and then use another pointer p2
which walks the list, and for each new node p2 visits it tests to see if
it's the one p1 points to. If there is a loop then you will discover
that in N increments, and the same is true if there's no loop.

If we look at the turtle and hare strategy we see that since the hare
moves twice as fast as the turtle it will make two laps (if there's a
loop) in the same time as the turtle makes one. So this means that we
will find if there's a loop in 3N increments with this strategy and if
there's no loop it will take 1.5N increments.

 

[JT]

What is it that I am missing here, wouldn't the simplest approach be to
store a pointer p1 to the "beginning" and then use another pointer p2
which walks the list, and for each new node p2 visits it tests to see if
it's the one p1 points to. If there is a loop then you will discover
that in N increments, and the same is true if there's no loop.

Your method works if the loop is a complete loop,
but it doesn't work (and in fact goes into an infinite loop)
if the loop begins half way.

Say Node1.next == Node2
and Node2.next == Node3
and Node3.next == Node2

Then the tortoise/hare method will find it.

 

[=?ISO-8859-1?Q?Erik_Wikstr=F6m?=]

Your method works if the loop is a complete loop,
but it doesn't work (and in fact goes into an infinite loop)
if the loop begins half way.

Say Node1.next == Node2
and Node2.next == Node3
and Node3.next == Node2

Then the tortoise/hare method will find it.

I see.

 

[dasjotre]

Let me try the 3rd time: (But surely, you get
the idea by now. Whether my quick code has bug
is irrelevant to whether this is a powerful classic technique)

right, I don't know what I was thinking. I read 'loop' and
though 'duplicate' 8:]

I get what you mean, both hare and tortoise get caught
in the same cycle and the step difference ensures they
eventually meet. neat.

regards

DS