C Puzzles

Email thread
---------------------------------------
At 10:51 AM 7/12/2005 +0530, Mahesh Gupta \(mahegupt\) wrote:
Hi...
Thanks for ur suggestion... That(temp2==NULL) is a very g8t point....otherwise whole code carry only Big 0 marks

Thanks
Mahesh

-----------------------------------------------------------------------
From: Joju Chevookaran (jchevook)
Sent: Tuesday, July 12, 2005 10:47 AM
To: Mahesh Gupta (mahegupt)
Cc: Manokar Namasivayan (nmano); Anand Rao (anarao); codc-bytes(mailer list)
Subject: Re: want to have some c puzzles..

Hi Mahesh,

There is a chance for seg fault. See inline

Mahesh Gupta (mahegupt) wrote:
Hi All
I m a new member..
I think we can find out the loop with use using only two temporary variables.. Please give ur comments

loop(node *ptr)
{
node *temp1,*temp2;
temp1=ptr;
if(temp1)
{
temp2=temp1->next;
}[joju] For single noded linked list, temp2 is NULL.

while(temp1&&temp2->next && temp1 != temp2)[joju] Here trying to access temp2->next.
Will face the same issue for a linked list with out loop.

{
temp1==temp1->next;
temp2=temp2->next->next;[joju] This looks good. will catch the loop somewhere, some time.

Only thing you need to do is add a checking for temp2 in while loop.
while(temp1&& temp2 && temp2->next && temp1 != temp2)

thats great :-).

Thank you,
Joju


}

if(temp1==temp2)
printf("The loop exist\n")
else
printf("There exist no loop\n");
}

Thanks
Mahesh

-----------------------------------------------------------------------
From: Manokar Namasivayan (nmano)
Sent: Monday, July 11, 2005 9:18 PM
To: Joju Chevookaran (jchevook)
Cc: Anand Rao (anarao); codc-bytes(mailer list)
Subject: RE: want to have some c puzzles..

hi Joju,
yes, bad algo. how about...

I Assume that total_elements is intact (not one that is found by looping the list (another issue).

find_loop()
{
/* declare temp1 and temp2 */

temp1 = head;
no_of_elements1 = no_of_elements2 = total_elements - 1;

while (temp1 != NULL) {

temp2 = temp1->next;
while ((temp2 != NULL) && (no_of_elements2)) {

if (temp1 == temp2) {
printf("\nfound loop");
return (1);
} else {
temp2 = temp2->next ;
--no_of_elements2;
}
}

if (!(!temp2 && !no_of_elements2)) {
printf("\nfound loop");
return (1);

}

temp1 = temp1->next;
no_of_elements2 = --no_of_elements1;

}

printf("No loop in the list");
return 0

}

thanks
Mano
-----------------------------------------------------------------------

From: Joju Chevookaran (jchevook)
Sent: Monday, July 11, 2005 8:45 PM
To: Manokar Namasivayan (nmano)
Cc: Anand Rao (anarao); codc-bytes(mailer list)
Subject: Re: want to have some c puzzles..

Hi Mano,

There is problem with this algorithm.

Suppose the linked list as follows.
Head -> node1 -> node2 -> node3 -> node4 ->node2

Inner while loop will enter into infinite loop.( temp2 will never equal to NULL)

Thanks,
Joju.
----------------------------------------------------------------
Manokar Namasivayan (nmano) wrote:

Hi Joju,
Fantastic...

Hi Anand,
Your algo is simply elegant one. I've not another solution (not simple
though).

find_loop()
{
/* declare temp1 and temp2 */

temp1 = head;

while (temp1 != NULL) {

temp2 = temp1->next;

while (temp2 != NULL) {

if (temp1 == temp2) {
printf("\nfound loop");
return (1);
} else {
temp2 = temp2->next;
}
}

temp1 = temp1->next;
}

printf("No loop in the list");
return 0

}


-----Original Message-----
From: Anand Rao (anarao)
Sent: Monday, July 11, 2005 6:45 PM
To: Joju Chevookaran (jchevook)
Cc: Manokar Namasivayan (nmano); codc-bytes(mailer list)
Subject: Re: want to have some c puzzles..


Hi,

Regarding finding a loop inside a linked list, If setting a flag in the
node is allowed (which is initially reset) then the following will be
better.
This doesn't need recursion or any search inside the array which may be
time consuming.

int findloop(node_t *head)
{
while (head != NULL) {
if (!head->visited) {
head->visited =1;
head = head->next;
}
else {
printf("found a loop in the linked list\n");
return 1;
}
}
printf("no loop found in the linked list\n");
return 0;
}

Thanks,
Anand

---------------------------------------
At 06:08 PM 7/11/2005 +0530, Joju John C wrote:


Hi Mano,

Here is my Answers for the puzzles.
...

2) Finding if there is any loop inside linked list.

Just Pseudo Code only

list * visited_list[BIG_ARRAY] ={0};

int any_loops( list * p)
{
if ( p == null ) return 0; // means no loops
search for "p" in "visited_list"
if present
return 1; // means loop identified.

add p in "visited_list".
return any_loops (p->next)

}

You may use "visited_list" as another linked list instead of array.

...