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? 11 1849
On Jun 20, 10:11 pm, Shraddha <shraddhajosh...@gmail.comwrote:
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.
On Jun 21, 7:11 am, Shraddha <shraddhajosh...@gmail.comwrote:
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.
--
James Kanze (GABI Software, from CAI) email:ja*********@gmail.com
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34
James Kanze wrote:
>
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)
On 21 Jun, 06:19, Naresh Rautela <nraut...@gmail.comwrote:
On Jun 20, 10:11 pm, Shraddha <shraddhajosh...@gmail.comwrote:
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.
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
On 21 Jun, 06:19, Naresh Rautela <nraut...@gmail.comwrote:
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.
On Jun 21, 1:20 pm, dasjotre <dasjo...@googlemail.comwrote:
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
On Jun 21, 1:33 pm, JT <jackt...@gmail.comwrote:
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
On Jun 21, 1:37 pm, JT <jackt...@gmail.comwrote:
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
On 2007-06-21 07:19, Naresh Rautela wrote:
On Jun 20, 10:11 pm, Shraddha <shraddhajosh...@gmail.comwrote:
>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.
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.
--
Erik Wikström
On Jun 21, 2:17 pm, Erik Wikström <Erik-wikst...@telia.comwrote:
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.
On 2007-06-21 16:21, JT wrote:
On Jun 21, 2:17 pm, Erik Wikström <Erik-wikst...@telia.comwrote:
>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.
I see.
--
Erik Wikström
On 21 Jun, 14:41, JT <jackt...@gmail.comwrote:
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 This thread has been closed and replies have been disabled. Please start a new discussion. Similar topics |
by: C++fan |
last post by:
Suppose that I define the following class:
class example_class{
public:
example_class();
void funtion_1();
void function_2();
protected:
|
by: Dream Catcher |
last post by:
1. I don't know once the node is located, how to return that node.
Should I return pointer to that node or should I return the struct of that
node.
2. Also how to do the fn call in main for that...
|
by: Kent |
last post by:
Hi!
I want to store data (of enemys in a game) as a linked list, each node will
look something like the following:
struct node
{
double x,y; // x and y position coordinates
struct enemy...
|
by: Steve Lambert |
last post by:
Hi,
I've knocked up a number of small routines to create and manipulate a linked
list of any structure. If anyone could take a look at this code and give me
their opinion and details of any...
|
by: Eugen J. Sobchenko |
last post by:
Hi!
I'm writing function which swaps two arbitrary elements
of double-linked list. References to the next element of list
must be unique or NULL (even during swap procedure), the same condition...
| |
by: joshd |
last post by:
Hello,
Im sorry if this question has been asked before, but I did search
before posting and couldnt find an answer to my problem. I have two
classes each with corresponding linked lists, list1...
|
by: Joerg Schoen |
last post by:
Hi folks!
Everyone knows how to sort arrays (e. g. quicksort, heapsort etc.)
For linked lists, mergesort is the typical choice.
While I was looking for a optimized implementation of mergesort...
|
by: theeverdead |
last post by:
Ok I have a file in it is a record of a persons first and last name. Format is like:
Trevor Johnson
Kevin Smith
Allan Harris
I need to read that file into program and then turn it into a linked...
|
by: Atos |
last post by:
SINGLE-LINKED LIST
Let's start with the simplest kind of linked list : the single-linked list which only has one link per node. That node except from the data it contains, which might be...
|
by: QiongZ |
last post by:
Hi, I just recently started studying C++ and basically copied an example in the textbook into VS2008, but it doesn't compile. I tried to modify the code by eliminating all the templates then it...
|
by: marktang |
last post by:
ONU (Optical Network Unit) is one of the key components for providing high-speed Internet services. Its primary function is to act as an endpoint device located at the user's premises. However,...
| |
by: Oralloy |
last post by:
Hello folks,
I am unable to find appropriate documentation on the type promotion of bit-fields when using the generalised comparison operator "<=>".
The problem is that using the GNU compilers,...
|
by: jinu1996 |
last post by:
In today's digital age, having a compelling online presence is paramount for businesses aiming to thrive in a competitive landscape. At the heart of this digital strategy lies an intricately woven...
|
by: tracyyun |
last post by:
Dear forum friends,
With the development of smart home technology, a variety of wireless communication protocols have appeared on the market, such as Zigbee, Z-Wave, Wi-Fi, Bluetooth, etc. Each...
|
by: agi2029 |
last post by:
Let's talk about the concept of autonomous AI software engineers and no-code agents. These AIs are designed to manage the entire lifecycle of a software development project—planning, coding, testing,...
|
by: isladogs |
last post by:
The next Access Europe User Group meeting will be on Wednesday 1 May 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM).
In this session, we are pleased to welcome a new...
|
by: TSSRALBI |
last post by:
Hello
I'm a network technician in training and I need your help.
I am currently learning how to create and manage the different types of VPNs and I have a question about LAN-to-LAN VPNs.
The...
| |
by: muto222 |
last post by:
How can i add a mobile payment intergratation into php mysql website.
|
by: bsmnconsultancy |
last post by:
In today's digital era, a well-designed website is crucial for businesses looking to succeed. Whether you're a small business owner or a large corporation in Toronto, having a strong online presence...
| |