Floyd’s tortoise and hare algorithm without math

This algorithm detects a cycle in a linked list using small memory usage.

A linked list can have cycles when multiple nodes link to the same node. The diagram below has a cycle due to nodes B and G linking to node C.

If cycles are not expected to be in a linked list, we need to detect them first. Floyd’s tortoise and hare algorithm is one of the solutions for detecting this cycle. This algorithm has 2 parts: finding the cycle, and finding the node starting the cycle.

Let’s look at the first part: finding the cycle. The idea is that a tortoise moves one link at a time from the starting node and a hare moves two links at a time from the starting node and if there is a cycle, they will meet each other. Here is the proof.

• The hare always moves faster than the tortoise, so the hare won’t meet the tortoise until reaching the end node if there is no cycle.
• If the tortoise comes into the cycle: CDEFG, the hare will pass through the tortoise and there is no way to pass the tortoise without meeting the tortoise.

Now let’s look at the second part: finding the node starting the cycle. Sometimes we want to know which node started the cycle. This algorithm continues from the first part where both the tortoise and hare meet on the same node. The tortoise keeps moving and a new tortoise starts to move from the starting node. The node both tortoises meet is the node the cycle starts. Here is the proof.

• After the same number of moves that happened in the first part happens in the second part, both tortoises will meet because the original tortoise moves the same links to the hare from the first part and the new tortoise moves the same links to the original tortoise from the first part.
• Before the same number of moves that happened in the first part happened in the second part, the tortoises moved together since they both move one link at a time.
• At the start of the second part, the original tortoise is at the node in the cycle and the new tortoise is not in the cycle. So if they don’t meet at the starting node of the cycle, they can never meet because they will move the cycle at the same distance to each other.
• Therefore the node both tortoises meet for the first time is the node that starts the cycle.
• One special case is where the cycle starts from the starting node. In this case, the tortoise and hare will meet at the starting node in the first part and both tortoises meet on the starting node with 0 moves in the second part.

Let’s apply this algorithm to the example linked list shown earlier. Applying the first part, the tortoise and hare meet on node F after 5 moves which prove that there is a cycle. Applying the second part, both tortoises meet on node C which is the start node of the cycle.