Proof of detecting the start of cycle in linked list

Question

From several posts inside stackoverflow and outside, I have come to know how to detect cycles in a linked list, the length of a cycle. I also found the method on how to detect the start of the loop.

Here are the steps again for reference.

Detecting Loop:

Have two pointers, classically called hare and tortoise. Move hare by 2 steps and tortoise by 1. If they meet at some point, then there is surely a cycle and the meeting point is obviously inside the cycle.

Finding length of Loop:

Keep one pointer fixed at meeting point while increment the other until they are same again. Increment a counter as you go along and the counter value at meet will be the length of cycle.

Find the start of cycle

Take one pointer to start of the list and keep the other at the meeting point. Now increment both by one and the meet point is the start of loop. I verified the method using some cases on paper, but I don't understand why it should work.

Can someone, provide a mathematical proof as to why this method works?

Answer 1

If you represent a list by a pointer to its first node (list)

The algorithm to detect loops is described as follows:

1. Declare two pointers (pFast) and (pSlow).
2. Make pSlow and pFast point to list.
3. Until (pSlow), (pFast) or both point to NULL:
   4. 
   5. 
   6. If , then STOP as a loop has just been found.
4. If this point has been reached (one or both two pointers are NULL) then there are no loops in the list.

Lets assume that this algorithm is correct. In this scheme, a loop situation is represented by the following diagram:

Note how every node, except the one pointing to the begining of a loop, is labeled with the number of its target minus one. So, if one node is labeled with i and it is not the begining of a loop, then it is pointed as next element by the node labeled with i-1.

The algorithm explained above can be described as a loop since its main step (3) is a set of sub-steps which repeated until the exit condition is satisfied. That forces us to represent pFast and pSlow in function of the iteration number in the algorithm execution (t).

If the list hadn’t have loops, pointers positions would be described in function of t as:

However there is a node where the loop starts and that function stops describing the evolution of the pointers. Assuming that this pointer is tagged with m, that the loop contains nodes (that is and ), and setting t=0 as iteration value when then:

If one pointer is indeed enough to detect loops using the algorithm described, then it must exist at least a solution to the equation .

This equation is true if and only if there is a value for t that makes:

This ends in a function, which generates values of t that are valid solutions to the equation described above:

Thus It is proved that one slow pointer and one fast pointer are enough to detect loop conditions in a linked list.

Answer 2

You can make your 'Find the start of cycle' proof simpler if you don't use meeting point.
Let second pointer start not at the 'meeting point', but M steps ahead of first pointer. (Where M is the length of the loop.)

This way, proof is pretty obvious. When the first pointer reaches start of the loop, second will be exactly M steps ahead: also at the start of the loop.

Answer 3

Distance travelled by slowPointer before meeting = x + y

Distance travelled by fastPointer before meeting = (x + y + z) + y = x + 2y + z

Since fastPointer travels with double the speed of slowPointer, and time is constant for both when the reach the meeting point.

So by using simple speed, time and distance relation 2(x+y)= x+2y+z => x+2y+z = 2x+2y => x=z

Hence by moving slowPointer to start of linked list, and making both slowPointer and fastPointer to move one node at a time, they both have same distance to cover .

They will reach at the point where the loop starts in the linked list.

Answer 4

The second part, stating that "to find the start of the loop, just move one pointer back to the start of the list then iterate both until they meet" is wrong!

It is correct only if the fast pointer has gone round the loop exactly once - i.e. that the portion before the start of the loop is shorter than the length of the loop - but if it is longer then the algorithm doesn't work; you can get stuck in an infinite loop.

Try it with a linked list with 11 elements, where the 11th points to the 7th:

1 1 -> 3 2 -> 5 3 -> 7 4 -> 9 5 -> 11 6 -> 8 7 -> 10 8 -> 7 9 -> 9 9

-- loop detected

Move one back to start and increment them: 1 9 -> 2 10 -> 3 11 -> 4 7 -> 5 8 -> 6 9 -> 7 10 -> 8 11 -> 9 7 -> 10 8 -> 11 9 -> 7 10 -> 8 11 ->...

Answer 5

/* Algorithm : P2 is moving through the list twice as fast as P1.
   If the list is circular, it will eventually get around P1 and meet */

public boolean hasCycle()
{
  DoubleNode p1,p2;
  p1=p2=firstNode;    //Start with the first loop

  try
  {
    while (p2 != null)     //If p2 reaches end of linked list, no cycle exists
    {
        p1=p1.next;   //Move to next
        p2=p2.next.next; //Move to 2 steps next
        if(p1==p2)
           return true;     //p1 and p2 met, so this means that there is a cycle
    }
  }
  catch(NullPointerException npe)
  {
      //This means that p2 could not move forward
      return false;
  }

  return false;
}