Fog Creek Software
Discussion Board




Link List #40

Hello, I just recently came across this site. I was reading through the archive and the answer to problem #40 Link List oses another question about breaking a loop in a link list in O(n) time and constant space. I have been thinking about this a while and can not seem to figure out a way to solve the problem. Does any one have any ideas or hints that might help me? Thanks

Jacob
Saturday, March 01, 2003

Yeah, I'd love to see the answer as well..

Adil
Monday, March 03, 2003

I actually found the answer to this question on an older post in this discussion forum given by Alex Harris. Here is the link
http://discuss.fogcreek.com/techInterview/default.asp?cmd=show&ixPost=710&ixReplies=8

He gives the solution in code with very little comments and it took me a day to figure out how the algorithm worked and the method used, so I thought I would go ahead and write a bit more detail explanation of how to solve this problem using Alex’s solution.

The solution assumes that you have already ran the algorithm (DetrmineLoop) to determine if the link list has a loop and that you are running this algorithm because you found a loop. Using the DetrmineLoop algorithm returns a point at which both the slow and fast pointer meet. Which will from now on be know as node Y. Y will always be some point with-in the loop and not be the last node in the list.

There are 2 types of loops that this algorithm deals with
    Loops that go from the end back to the beginning
    Loops that go from the end to some point in the middle (non-head node)

For the point of this conversation, it is best if we look at the second case, the first is really only really a special case of the second.

So our list will look something like this (where the 11th node points the 4th Node)

Outside                          Inside
                            Y
0->1->2->3->-4>5->6->7->8->9->-10>11|
                        ^--------------------------------
        S

Y can be any node in the loop [except the last] (in general)
In this case it is 5.

Our goal is to find S, this is the start of the loop. Once we found this we can break the loop, by either counting the number of node inside and outside the loop or by searching for the second node that points to S.

What we do now, is to create 3 pointers that will keep track of important points within the list. Namely A,B,C

We initially set A to the head of the list. In this algorithm, A is used as a point outside the loop. The idea is to move A as close to the start of the loop(S) as possible. A will only move right.  It is possible for A to equal S or to move A so that it equals S. However A should not be moved any further right. (I am pretty sure on this last sentence but not 100%) A is considered the left pointer.

The second pointer C (Alex probably should have switched the pointer names of C and B, but it doesn’t really matter : ) is one of two pointers inside the loop. C will always be to the left of B (or equal too). It will also be to the right of or equal to A.  It is initially set to Y.  C will only move left and can be considered the middle pointer.

The third pointer B starts 1 to the right of C and stays to the right of C (except if it comes around and equals C.) B considered the right pointer and only moves right.

So visually we have something like this (initially)

A                        C  B
0->1->2->3->-4>5->6->7->8->9->-10>11|
                        ^--------------------------------

Now the idea is to keep moving all the pointers closer to S. A and B keep moving right and C will move left (they may not need to move at all if they equal S).

We move the pointers in the following ways.

First we find the midpoint between A and C. Midpoints can be found by setting 1 pointer to move 2 spaces while the other move 1, similar to DetrmineLoop. Here is my code for it. (it assumes that there is a loop and we are not going to find any nulls) We round to the left or begging of the list.

node *midpoint(node *a,node * b){
  node *slow = a, *fast = a;

  while((fast != b) &&(fast->pNext != b)){
    fast = fast->pNext->pNext;
    slow = slow->pNext;
  }
  return slow;
}

Once we have this midpoint T we see if it inside or outside the loop.

We do this by searching from B to C. The C++ code uses a function called find, which just iterates from B to C comparing each pointer against T. If we find T in this “find” then T is inside the loop.

If it is inside we set C=T (moving it left) other wise we set A = t->next (moving it right). If T is the node before S (thus outside the loop) we will be setting A to S and this is the only time A will be inside the loop.

Next we find the midpoint between B and C named T(2) [we do not need to declare another pointer but I would like to distinguish the two]. Then determine if this mid point is to the left or right of C.

To find if T2 is to the left or right of C we do another “find” from A to C. If we find it then it is on the left (remember A is always on the left of C.)

If it is to the left then we set C=T2 otherwise we set B=T2.

The reason we are doing this is because we do not need to search the entire loop to figure out if our first midpoint T is in the loop. T will be between S and C (if it is in the loop) so the further we move B down the less we have to search.

We then repeat the process of finding the midpoints and moving pointers until any 2 pointer (A,B or C) equal each other.

A will only move right as long as T is outside the loop. So if A is ever inside the loop A=S and will stop moving. B will move right until it reaches S (we loop) as well and then will stop. C will move left (possibly twice in the loop) until it reaches S.

So what is going on is that the pointers are closing in on S. Its possible for one pointer to equals S while the others do not. However we KNOW we found S when two pointers equal each other and S.

At the end is my C++ code for the function I wrote to implement this

As far as efficiency:
This algorithm uses constant space, we declare about 5 pointers. We use a few more for our helper functions as well.

Now for time; DetrmineLoop runs in O(n) and is only ran once. The big time killers are the functions find and midpoint. In the worst cases they will take n steps the first time through the loop. But notice we cut the range in half every time we iterate the while loop.
So the second time it ran in n/2 and the third is n/4. So if we add up our not so infinite series I believe we get on the order of n steps. (It has been a long time since I did infinite series and I was really bad at it :)

As far as the special case where the end points to the beginning the algorithm still works. The only thing is that A never moves.


Node *LinkList::findLoop(){

//This run the DetrmineLoop algorithm and gives us back Y
  node * y = DetrmineLoop ();
  node * t;
  node * a =pTop; //pTop is the head of the list
  node * b =y->pNext;
  node * c =y;

  while (1) {
    t=midpoint (a,c); //finds the mid point between A and C
    if (find (b,t,c)) //is t in the loop?
      c=t; // move C left
    else
      a=t->pNext;  // move A right

    t= midpoint (b,c); // a point inside the loop
    if (find (a,t,c)) //is t2 left or right of C
      c=t; //It is to the left so move C left
    else
      b=t->pNext; //It is to the right so move B right

    if (a==b) {
      return a;
    }
    if ((a==c) || (b==c)){
      return c;
    }
  }
}
////////////////////////////////////////////////////////////////////////
bool find(node *a,node*b,node*c){
  node *curNode = a;
  while(curNode != c){
    if(curNode == b)
      return true;
    curNode = curNode->pNext;
  }
  return false;
}

Jacob Blumberg
Monday, March 03, 2003

My diagram of Y and S when pasting into this did not come out just right. Y is the 5th node and S is the 4th.

Jacob Blumberg
Monday, March 03, 2003

*  Recent Topics

*  Fog Creek Home