Flyod's Cycle Detection Algorithm (Tortoise and Hare Algorithm)

Recently i came across an interesting problem on "how to detect cycles in a linked list?". Digging into that i figured out this famous algorithm Flyod's cycle detection algorithm(aka Tortoise and Hare algorithm) on how to detect whether a linked list is cyclic.

What is a cycle?

Linked list is basically a serious of nodes (object) point to the other and form a chain so that you can traverse, insert or delete an element from the list. Circular linked list is a type of list where the last node points to the first node. Cycles are something different from circular list, where the last node is pointing to a different node other than the "head or start" node.

Sample cycle

How to detect this cycle?

The algorithm goes this way

1. Have two nodes "tortoise" and "hare" both holding the reference of the starting of the list.

2. Check whether "hare's" next is there or not and make the pointer to move 2 hops.

3. Make the "tortoise" to make one hop.

4. At some point of time if both "hare" and "tortoise" are same then your list is cyclic.

Code for the algorithm

public boolean hasCycle(Node first) {

            if(first == null) // list does not exist..so no loop either.

       return false;

   Node tortoise, hare; // create two references.

   tortoise = hare = first; // make both refer to the start of the list.

   while(true) {

       tortoise = tortoise.next;          // 1 hop.

       if(hare.next != null)

           hare = hare.next.next; // 2 hops.

       else

           return false;          // next node null => no loop.

       if(tortoise == null || hare == null) // if either hits null..no loop.

           return false;

       if(tortoise.equals(hare)) // if the two ever meet...we must have a loop.{

       {

        return true;

       }

       

   }

}

Note : The whole code is shared as a link below. This contains the code to create the whole linked list, making it as cyclic and then identify whether its cyclic or not.

TortoiseHareAlgorithm.java