finding the point where a loop begins

[dude543]

This is/was an interview question I got two weeks ago.
Find where the loop begins in simple linked list.
I hope this figure will help understand what I mean :

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

If not the figure take a look at this where I make the error.

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 */
/* Not its value of course but its address */
getchar();
return(0);
}

My solutions :
1) If we have a filed in the struct which his value
is known to us. We can loop throw the list checking
if it is the value known to us, else chaning it to something else.
When we encounter the changed value, the previous cell
is the beging of the loop.
2) Allocating an array of pointers. Looping throw the list
and adding its address to the array. Every time we had
a new address we check if it is not in the array.
If it is in the array the previous cell is the beging
of the loop.

Anybody has other solutions ?
Thanks in advance.

[Lerner]

To me node three is the start of the loop, not node two or node 10, both of which point to node three. I agree that node 10 is where the error is, if you are looking for the error, but it isn't where the loop begins, IMO.

In any case, I think the second protocol you describe seems most likely to succeed, though I'm not sure the code you posted reproduces the loop you drew. In particular I question why you made pptemp a pointer to pointer instead of just a pointer. The following makes more sense to me, though I admit I have not compiled either your version or mine.

//declare node struct to create list from
 struct list 
 {
     int  val;
     list *pnext;
 } 

int main()
{
    list *phead, *plast, *ploop, *pptmp;  //pointers to use 
    int    i;

    for ( i = 1 ; i <= 10 ; ++i )  //create total of 10 list objects
    {
      //declare memory for a new list object
      pptmp  = new list ;        

      //initialize each objects member variables
      pptmp->val = i;
      pptmp->pnext = NULL;

      //keep track of the desired place to create the loop
      if ( i == 3 )
        ploop = pptmp;

      //create the list 
      if(i == 1)
        plast = phead = pptemp;
      else
      {
        plast->next = pptmp;
        plast = plast->pnext;
      }
    }
 
 
  /* Doing the error !!!!!!!!!! */
  /*create the loop*/
  plast->pnext = ploop;
 
 
  /* Trying to find the error. e.g. cell 10 */
  /* Not its value of course but its address */
  getchar();
  return 0;
}

[Salem]

> 1) If we have a filed in the struct which his value is known to us
Seems good to me - no extra storage needed, like working out how to allocate a big enough array of pointers. Also, checking time increases with the length of the list.

Call the new member say bool seen;

while ( node && !node->seen ) {
  node->seen = true;
  node = node->next;
}
if ( node ) {
  // I'm the start of the loop
}

[dude543]

Thank you guys, Lerner and Salem.
But I wasnt interstead in the way to implenent the code.
But rather, other ideas then mine to find node 10.

[dude543]

Any more ideas ?

[Salem]

How many more ideas do you want?

You already have two perfectly feasible answers.

Or is this a game of "guess which answer the interviewer" decided was the right approach?

How about
- a solution based on sets
- a solution based on hashes
- a solution based on strings

Pick any other data structure you like which has some concept of "membership" and try that.

[dude543]

How many more ideas do you want?

I apologize for upsetting you.
Sorry.

But maybe someone else will have a better solution.

[Lerner]

I think "better" is in the eye of the beholder. For example: is it better to be short and obfuscated or lenthy and perfectly readable. Answer: Depends on what constraints you have. If memory is at a premium it's better to be short and obfuscated. If not, it's better to lenthy and perfectly readable. In this setting I would choose an approach I could justify and be able to explain clearly why I'm doing what I'm doing. That way even if I don't happen to hit the format "desired", if there is a format desired, I can defend my approach. Often it's not whether you get the right answer but how do approach the problem, how do you communicate your approach, and then if it isn't working out for you alone, someone else can help you come up with a workable solution, a more palatable solution, a "better" solution.

[Rashakil Fol]

I think a good solution is to check if you've reached a node the second time only on nodes whose distance from the beginning is a power of two. This lets you find a loop in linear time. From this you can also use divide and conquer to find the starting point of the loop in linear time.

Using a hash would also be linear time (usually), but probably slower.

[dude543]

Thanks All.