# Finding a loop in a singly linked list

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.