Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Proof of detecting the start of cycle in linked list [duplicate]

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?

like image 743
Shamim Hafiz - MSFT Avatar asked Oct 17 '10 10:10

Shamim Hafiz - MSFT


People also ask

What is the optimal way to detect a loop in a double linked list?

Method 2 (Better Solution)Let the count be k. Fix one pointer to the head and another to a kth node from the head. Move both pointers at the same pace, they will meet at the loop starting node. Get a pointer to the last node of the loop and make the next of it NULL.

How the starting node can be identified in a circular link list?

In a circular linked list, we start from the next of the last node which is the first node and traverse each node. We stop when we once again reach the first node. Thus to the last node 50, we again attach node 10 which is the first node, thereby indicating it as a circular linked list.


1 Answers

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

enter image description here

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:
    1. enter image description here
    2. enter image description here
    3. If enter image description here, 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:

enter image description here

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).

enter image description here

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

enter image description here

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 enter image description here and enter image description here), and setting t=0 as iteration value when enter image description here then:

enter image description here

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

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

enter image description here

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

enter image description here

enter image description here

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

like image 55
Pablo Francisco Pérez Hidalgo Avatar answered Sep 22 '22 23:09

Pablo Francisco Pérez Hidalgo