loop in a single linked list

[sonu]

Hi All,

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

 

[zhousqy]

one way is to mark the element you visited

 

[sonu]

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

 

[jitu.csewizard]

*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 ....

 

[sonu]

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

 

[Default User]

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

 

[santosh]

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/>

 

[santosh]

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/>

 

[jitu.csewizard]

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

 

[zhousqy]

santosh 写é“：

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/>

 

[zhousqy]

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!!