One of the most common interview questions for software professionals is "How do you find a loop in a singly linked list?". Most of the people tend to think in the recursive way to solve this problem. The truth is that the most optimal solution for this problem lies out of the scope of the linked list.

A linked list with a loop can be visualized as a pseudo-random number sequence where the pseudo-random numbers are the addresses (pointers) of each node. After some time, the cycle repeats itself. There are two factors in the sequence now. One is the length of the cycle and other one is the length of the tail (the non-repeating part). Robert W. Floyd invented the Floyd's cycle-finding algorithm in 1967 based on the properties of the pseudo-random sequences. By applying this algorithm, we simultaneously go through the list by ones (slow iterator) and by twos (fast iterator). If there is a loop the fast iterator will go around that loop twice as fast as the slow iterator. The fast iterator will lap the slow iterator within a single pass through the cycle. Detecting a loop is then just detecting that the slow iterator has been lapped by the fast iterator. It is sometimes called the "tortoise and the hare"-algorithm.

Here is a sample implemetation of this algorithm in C.

typedef struct node_s {
    void *data;
    struct node_s *next;
} NODE;

int list_has_cycle(NODE *list)
{
    NODE *fast=list;
    while(1) {
        if(!(fast=fast->next)) return 0;
        if(fast==list) return 1;
        if(!(fast=fast->next)) return 0;
        if(fast==list) return 1;
        list=list->next;
    }
    return 0;
}

If one wants a much more readable implemenation of this algorithm, here we go!

int list_has_cycle(NODE *list)
{
    NODE *s = list, *f1 = list, *f2 = list;

    while( s && f1 = f2->next && f2 = f1->next ) {
        if ( s == f1 || s == f2 ) {
            return 1;
        }
        s = s->next;
    }
    return 0;
}

This is the best solution known so far for the given problem as it is of O(n) time and O(1) space. There are some other algorithms known of O(nlogn), O(n^2) time and a hash table based algorithm of O(n) time and O(n) space.