By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
429,334 Members | 2,776 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 429,334 IT Pros & Developers. It's quick & easy.

loop in a single linked list

P: n/a
Hi All,

here i have a daught how can i find wheather a linked list contains a
loop or not.

Mar 27 '06 #1
Share this Question
Share on Google+
10 Replies


P: n/a
one way is to mark the element you visited

Mar 27 '06 #2

P: n/a
suppose my node contains like the following declaration.

struct node
{
int info;
struct node *next_ptr;
}
then how can i mark the node is visited or not.
please specify the code

Mar 27 '06 #3

P: n/a
*if the linked list is read only, take two pointer approach..both
pointing to beginning of linked list. now increment p1 by 1 and p2 by 2
and compare both. if they are equal there is a cycle. repeat this
untill p2 points to null.

*if u have the condition not to modify the node but u can change the
links, then reverse the linked list. if u reach the head node then
there is a cycle ....

Mar 27 '06 #4

P: n/a
Can u wtite the code. suppose we have 100 nodes then 100 node is
pointing 49the node then what will be the situation

Mar 27 '06 #5

P: n/a
sonu wrote:
Can u wtite the code. suppose we have 100 nodes then 100 node is
pointing 49the node then what will be the situation

Please don't use abbreviations like "u". They make your post extra hard
to read. Also, notice how almost everyone else quotes the previous post
in replies? You should as well. See below.

Brian

--
Please quote enough of the previous message for context. To do so from
Google, click "show options" and use the Reply shown in the expanded
header.
Mar 27 '06 #6

P: n/a
zh*****@gmail.com wrote:
sonu wrote:
Hi All,

here i have a daught how can i find wheather a linked list contains a loop or not.
one way is to mark the element you visited


You've already been requested to include context in your posts. Notice
this reply to you, wherein, I'm quoting both you and the poster before.
This ensures that each post is semi-independent and can be easily
understood by readers who may use an unthreaded newsreader or those who
may be reading your post after the previous ones have expired. *Please*
read the material at the following URLs:

<http://cfaj.freeshell.org/google/>
<http://clc-wiki.net/wiki/Introduction_to_comp.lang.c>
<http://www.safalra.com/special/googlegroupsreply/>

Mar 27 '06 #7

P: n/a
sonu wrote:
suppose my node contains like the following declaration.

struct node
{
int info;
struct node *next_ptr;
}
then how can i mark the node is visited or not.
please specify the code


You could define a member of type bool whose initial value could be
false, and which you can set to true after you've visited the node.

Oh, and by the way, include context in your posts, where possible.
Please review the following URLs:

<http://cfaj.freeshell.org/google/>
<http://clc-wiki.net/wiki/Introduction_to_comp.lang.c>
<http://www.safalra.com/special/googlegroupsreply/>

Mar 27 '06 #8

P: n/a
the code for the first method goes as

#include <stdio.h>

struct node
{
struct node *next;
int data;
}

int main()
{
struct node *list, *p2, *p1;

load_list_somehow(&list);

/* Test trivial no-loop and trivial loop */
if (list == NULL)
{
/* No loop, uninitialised list */
printf("No loop\n");
}

if (list->next == list)
{
/* Trivial loop */
printf("Loop detected\n");
return 0;
}

p1 = list;
p2 = list->next;

while (p2 != NULL && p1 != p2)
{
/* Increment p1 once, p2 twice */
p1 = p1->next;
p2 = p2->next;
if (p2 != NULL)
p2 = p2->next;
}

if (p2 == NULL)
{
/* We got to the end of the list */
printf ("No loop\n");
}
else
{
/* p1 == p2, and the p2 "lapped" the p1
* in the loop */
printf ("Loop detected\n");
}
return 0;
}

the second method is obvious , try reversing a linked list with a cycle
...you will realize.

i hope the solution is clear enough
there is on more most efficient solution of this problem:
if you want to go through it try google on
Floyd's cycle-finding algorithm or The Tortoise and the Hare Algorithm

enjoy
thanks
jitendra

Mar 27 '06 #9

P: n/a

santosh 写道:
zh*****@gmail.com wrote:
sonu wrote:
Hi All,

here i have a daught how can i find wheather a linked list contains a loop or not.

one way is to mark the element you visited


You've already been requested to include context in your posts. Notice
this reply to you, wherein, I'm quoting both you and the poster before.
This ensures that each post is semi-independent and can be easily
understood by readers who may use an unthreaded newsreader or those who
may be reading your post after the previous ones have expired. *Please*
read the material at the following URLs:

<http://cfaj.freeshell.org/google/>
<http://clc-wiki.net/wiki/Introduction_to_comp.lang.c>
<http://www.safalra.com/special/googlegroupsreply/>


Mar 28 '06 #10

P: n/a
santosh wrote:
zh*****@gmail.com wrote:
sonu wrote:
Hi All,

here i have a daught how can i find wheather a linked list contains a loop or not.

one way is to mark the element you visited


You've already been requested to include context in your posts. Notice
this reply to you, wherein, I'm quoting both you and the poster before.
This ensures that each post is semi-independent and can be easily
understood by readers who may use an unthreaded newsreader or those who
may be reading your post after the previous ones have expired. *Please*
read the material at the following URLs:

<http://cfaj.freeshell.org/google/>
<http://clc-wiki.net/wiki/Introduction_to_comp.lang.c>
<http://www.safalra.com/special/googlegroupsreply/>


Thanks for your suggestion!!

Mar 28 '06 #11

This discussion thread is closed

Replies have been disabled for this discussion.