how to find loop

[johnray31]

hello friends could anybody give me idea how i can find a loop in simple linked list

[Narue]

If this is the common interview question then you want two iterators, one skipping ahead by a single node each step, and one skipping two nodes. If the two iterators meet before the end of the list, you've found a loop.

If this is not the common interview question, be more specific.

[johnray31]

If this is the common interview question then you want two iterators, one skipping ahead by a single node each step, and one skipping two nodes. If the two iterators meet before the end of the list, you've found a loop.

If this is not the common interview question, be more specific.

thankx yar it was a common interview question i gave answer but my interviewer was not satisfied..... i think ur answer was the correct way to satisfiy him.

anyway thankx again

[dude543]

By saying "how i can find a loop in simple linked list"
do you mean like in my little drawing ?
( In a "normal linked list cell 10 would have point to NULL")

[1] ->[2] ->[3] ->[4] ->[5] 
             ^           |
             |           U
            [10]        [6]
             ^           |
             |           U
            [9]<- [8]<- [7]

and the question was to find cell 10 ?
How does "you want two iterators, one skipping ahead by a single
node each step, and one skipping two nodes. If the two iterators
meet before the end of the list, you've found a loop." ?
this help finding cell 10 ?

My small program

int main(void)
{
struct list 
  {
  int  val;
  struct list *pnext;
  } *phead, *plast, *pptr, *ploop, **pptmp, *p1, *p2;
int    i;
phead = NULL;
pptmp = &phead;
for ( i = 1 ; i <= 10 ; ++i )
   {
   plast = (*pptmp) = malloc(sizeof(*phead)) ;
   (*pptmp)->val = i;
   (*pptmp)->pnext = NULL;
   if ( i == 3 )
       ploop = (*pptmp);
   pptmp = &(*pptmp)->pnext;
   }
 
/* Doing the error !!! */
plast->pnext = ploop;
 
 
/* Trying to find the error. e.g. cell 10 */
for ( p1 = phead->pnext,
      p2 = phead->pnext->pnext
                    ; p1 && p1->pnext &&
                      p2 && p2->pnext && p2->pnext->pnext ;
                             p1 = p1->pnext,
                             p2 = p2->pnext->pnext )
    if ( p1 == p2 )
        break;
printf("p1->val = %d\n", p1->val);
printf("p2->val = %d\n", p2->val);
getchar();
return(0);
}

The results :
p1->val = 9
p2->val = 9

and should have been 10.

[Narue]

>By saying "how i can find a loop in simple linked list"
>do you mean like in my little drawing ?
No, the OP meant "How do I determine if there's a loop in a linked list". This is/was an interview question where you start out given the basic question, and then restrictions are added until you reach the final conclusion of using two iterators.

Actually finding the point where a loop begins is a different problem. The two iterator solution will find a loop, but when they meet, they won't necessarily be at a meaningful node for figuring out where the loop began.

[dude543]

Thanks.

I tougth so, but wanted to be sure.
At least you figured out my figure,
which means that my drawing skills
are improving.

Thanks again.