Cycle detection in linked lists

Find if a linked list has a cycle given a pointer to it's first element.

There are several ways of solving this problem.

• iterate over the list and insert elements into a hash table. We have a cycle if we insert the same element twice. This solution requires 0(n) time and 0(n) memory.


• adapt the list to this particular situation. Insert a field that marks the node as visited or not. This solution has the drawback of modifying the list which is not always possible.


• Floyd algorithm which will be presented below its an efficient and easy to understand algorithm and requires O(n) time and O(1) additional memory.

Also known as the tortoise and hare algorithm it uses two pointers a and b , where a moves two times faster than b.
The pseudocode for the algorithm is as follows:

 
      a <- list_head
      b <- list_head
      do
           a <- a.next.next
           b <- b.next
      while a <> b 
//if there is a cycle then a will be equal at some point with b. 

An immediate application of Floyd's algorithm is retrieving the element in the middle of a list without computing it's length.