Floyd’s Hare and Tortoise Algorithm Demo

Floyd’s algorithm is used to find cycles in linked lists. It’s a smart and simple approach to find the starting node of a cycle with O(n) time complexity and O(1) space complexity.

We’ll start by a description of a common algorithm to find cycles, then continue to briefly explain Floyd’s algorithm, and finally show an interactive demo of it.

-> Skip to the demo

Regular algorithm to find cycles

A very simple approach to find cycles in a linked list would be as follows:

previous = new Map()
while (node = next(node)) {
  if (previous.has(node))
    return true
  previous.add(node)
}
return false

This algorithm visits every node in the linked list and stores the previously visited nodes. If at any time the node is part of the previous nodes, then we have a cycle. If we reach the end of the linked list, we break out of the loop. In that case, there is no cycle.

This simple algorithm is O(n) in time complexity. Every node is visited at least once. It’s also O(n) in space complexity. We store a list of all of the previously visited nodes.

Floyd’s algorithm

Floyd’s algorithm is implemented using two-pointers. One, the tortoise, moves one node at a time. The other, the hare, moves twice as fast. If the linked list is cyclic, the hare will eventually cross the tortoise after it has entered the cycle. It’s similar to runners in a circular track, with the fastest runners eventually crossing the slower ones.

First phase

Floyd’s algorithm is divided into two phases. In the first phase, both the hare and the tortoise start at the head of the linked list. They advance through the linked list, each at its own pace. The first phase finishes when the hare reaches the end of the linked list (there is no cycle), or when it reaches a node where the tortoise is at. Note that we compare only the node currently being visited by the hare, not the two that it traverses during each step.

Second phase

This phase takes place only if the hare reaches a node that the tortoise is currently visiting. Then, the tortoise pointer is moved back to the head of the linked list. The hare stays at its initial node. Next, both the hare and the tortoise start moving one node at a time. Floyd’s algorithm guarantees that the node where they meet again is at the start of the cycle!

For a mathematical explanation of why they’re guaranteed to meet at the start of the cycle, check this video.

Floyd’s Algorithm Demo

Finally, for the most interesting part of this blog post, an interactive demo of Floyd’s algorithm!

To start, set the size of the linked list and the desired size of the cycle using the slider inputs. Then, click on the next button to start the demo and keep pressing it to advance the demo. The simulation stops when the end of the linked list is reached or Floyd’s algorithm is completed. Press reset to start again.

• Visit the Codepen if the demo does not display correctly.