Question: Usually a singly link list always ends in null pointer. What if there is no null pointer; what if you are stuck in an infinite loop? If you have a singly link list head pointer, detect if there is a loop in the list or not.

Example:
The loop may start at the very beginning of the link list as well (like a circular singly link list.)

Answer: If you have ever watched a race in Olympics athletics event, you should be aware of the circular tracks. Lets take the example of 100m race; it takes place on a section of circular ground and has the dead end. So that a perfect example of a legitimate link list (have a null pointer at the end.)


A 1000m race also takes place on a circular track but athletes have to make multiple rounds of the same track (we can say this track as a loop in the list.) What if there is no finish line, an athlete has to run forever (because of no null pointer in the end.) Now if athlete X runs faster than athlete Y, X is bound to leave Y behind at some point. In the process, there will be a time when X and Y are at same place.

Similarly, if we traverse the link list using a slow iterator and a fast iterator, both the iterators will be at same node at some time if there is a loop. If there isn’t any loop, fast iterator will reach the end (null pointer) first. Detecting a loop is then just detecting that the fast iterator has lapped the slow iterator or not.

Code: I have written the following code assuming slow iterator moves one node at once and fast iterator moves 2 nodes at once.
bool hasLoop(list *head)
{
list *slow, *fast;
slow = fast = head;

while (slow && fast )
{
 slow = slow->next;
 fast = fast->next;

 if (fast)
     fast = fast->next;
 else
     return false;  //dead end

 if (slow == fast)  //loop detected
     return true;
}

return false;
}

Efficiency: Since both the iterators are traversing through the list at most twice in this case, so complexity is O(2*n) = O(n).

Further thoughts: Readers should find the optimal speed of fast iterator? Is there an effect on efficiency if we move fast iterator at a speed of 3 nodes per iteration in place of 2?

We have detected if there is a loop or not. Next task is to find where the loop starts. Give it a thought before I write a post for that.


Subscribe - To get an automatic feed of all future posts subscribe here, or to receive them via email go here and enter your email address in the box. You can also like us on facebook and follow me on Twitter @akashag1001.