Tortoise and Hare Algorithm : Detecting Loop in Singly Linked List (Random CS101s #02)

In this weeks, 'Random CS101s' post we are writing about another computer algorithm that has an interesting name : Tortoise and Hare Algorithm.

'Tortoise and Hare Algorithm' is a common name for the Floyd's cycle-finding algorithm which is use to detect cyclic loops in a singly linked list. The algorithm uses two pointers which moves through the sequences in the linked list at different speeds.

The tortoise pointer moves ahead by one step at a time and the hare tortoise moves ahead by two steps at a time. If the two pointers meet before anyone of the reaching the tail of the list, then there is an occurance of cyclic loop in the list.

The pseudo code for the Tortoise and Hare algorithm goes as follows:

Start the pointers tortoise and hare at the first node of the list
Do while (tortoise != NULL) AND (hare != NULL)
{
	tortoise = tortoise.next  //totoise pointer: move ahead by one step
	if(hare.next != NULL)
	{
		hare = (hare.next).next  //hare pointer: move ahead by two steps
	}

	if(tortoise == hare)
	{
		Output "Loop Found"
		Exit program
	}
}
Output "No Loop found"
Exit program

Complexity:
Time Complexity : O(n)
Space Complexity: O(1)

Since the tortoise pointer always moves in single step, the two will surely meet at some point before the tortoise moves through all the n nodes of the sequence.