Floyd’s Cycle Detecting Algorithm Explained

Today we’ll discuss Floyd’s algorithm to detect cycles in a linked list. This algorithm uses two pointers, one fast and one slow, in order to find where a linked list cycles. An example of this problem can be found here.

The idea of this algorithm is to progress through a linked list and keep track of 2 nodes. We start at the beginning (head) of the given linked list. We assign that node as the “slow” pointer. We assign the next node the “fast” pointer. Next, we start stepping through the list as long as the fast and slow pointer are not pointing at the same node. With each iteration, we set the slow pointer to the next pointer, and set the fast pointer to the next, next pointer.

At first glance, it may seem mysterious why this algorithm works. Lets walk through an example to see it working in action.

Imagine a linked list with 5 nodes, and on the fifth node, it cycles back to the third node. We assign the fast and slow pointers. Move the slow pointer by one (node 1 -> 2), and the fast pointer by two(node 2 -> 3 -> 4). Check if the pointers are equal. They are not. Repeat, move the slow pointer by one (node 2 -> 3), and the fast pointer by two (node 4 -> 5 -> 3). Check if the pointers are equal. They are. We have now identified the cycle.

When the fast pointer moves, if there is a cycle in the list, it will eventually meet the slow pointer.

Here is the algorithm in Ruby code:

Fast and slow pointers can be very useful, as we’ve seen with Floyd’s algorithm. Try and use this algorithm in future problems you encounter.