Tortoise & Hare Algorithm

Tortoise & Hare algorithm is also known as Floyd's Cycle-Finding Algorithm.This is a technique for detecting infinite loops inside a linked list, symlinks, state machines etc.

To detect a loop inside a linked list
Source

• Make a pointer to start of the linked list and call it Hare 
• Make a pointer to the head of the linked list and call it Tortoise 
• advance the Hare by two and the tortoise by one for every interation.
• There's a loop if the Tortoise and Hare meet
• There's no loop if the Hare reaches the end.

Algorithm is intersting as it takes O(n) time and O(1) space.

Python code to understand Tortoise and Hare algorithms
Source

def floyd(f,x0): tortoise=f(x0) hare=f(f(x0)) while tortoise!=hare: tortoise=f(tortoise) hare=f(f(hare)) mu=0 tortoise=x0 while tortoise!=hare: tortoise=f(tortoise) hare=f(hare) mu+=1 lam=1 hare=f(tortoise) while(tortoise!=hare): hare=f(hare) lam+=1 return lam,mu


With this Algorithm we detect the loops and iterations in a circularly linked list as suggested by the name Floyd's Cycle-finding Algorithm.

More Reference: Coding Freak