Tortoise and Hare algorithm

In last post I discussed an algorithm to find out intersection point in 2 lists. A related problem to that is to figure out if a list has cycles. Say there are 10 nodes in list and 10th node is pointing back to 4th node. How ill we figure out if a list has such a cycle.

There can be many solutions, like storing previously traversed nodes, or simply adding a flag to each node indicating of the node was already traversed or not. But these solutions need extra space of order n.

A classic solution to above problem is ‘Tortoise and Hare algorithm’ or ‘Floyd’s cycle-finding algorithm’. The idea is to have two pointers, one will traverse list node by node or move one node at a time (tortoise) and another pointer moving two nodes at a time (hare). If the list has a cycle, the two pointers are bound to meet at some node, otherwise they will never meet. Try to dry run it, you will know what it means.