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.