Understanding Floyd's cycle finding algorithm

Sometimes, a linked list may not terminate at a null reference but instead, hold the reference to some other node in the next section of its last node. Such a list is said to have a cycle, as now, if we traverse the list from the start, we will loop indefinitely and never reach a null reference. Floyd's algorithm, also called the tortoise and hare method, uses the fast and slow pointer technique to identify if a linked list has a cycle in a single pass. It is a really efficient algorithm that can also identify the node at which the cycle starts without using any extra space.

Algorithm

Floyd's cycle finding algorithm uses the fast and slow pointer technique to move two pointers through the list until they meet each other. We use two references, slow and fast initialized with the head node, traverse the list using fast. In each iteration, we move fast two steps ahead while slow only moves 1 step. If they both reach the same node at any point in the traversal, it means there is a cycle; otherwise, fast will eventually hit null at the end of the list, meaning the list does not have a cycle.

Below is an example of a linked list that has a cycle.

Once we confirm that a linked list has a cycle, the next step is to find where the cycle starts. After the fast and slow pointer meet at some node, we move fast back to the head of the list and traverse the list again using both fast and slow. However, this time, both fast and slow move at the same speed of one step in each iteration until they meet. The node at which they meet this time is where the cycle starts.

The algorithm given below summarizes the Floyd's cycle finding algorithm

• Step 1: Initialize references `slow` and `fast` with the head of the list.
• Step 2: Loop while `fast` and `fast.next` are not `null` and do the following:
  • Step 2.1: Move ahead `slow` by one step and fast by two steps
  • Step 2.2: Check if `slow` == `fast`. If yes, break out of the loop as the list has a cycle.
• Step 3: If `slow` != `fast` it means the list doesn't have a cycle, so terminate. Otherwise, continue to the following steps.
• Step 4: Set `fast` to the head of the list
• Step 5: Loop while `fast` and `slow` are not equal and move both one step in each iteration
• Step 6: Return `slow` as the node where the cycle starts.

Implementation

The implementation is relatively straightforward: We use the slow and fast pointer technique to traverse the list until the slow and fast points meet. In the case of a cycle, we repeat the steps once more with slight modifications.

Proof of correctness

Floyd's cycle-finding algorithm can detect cycles and find where the cycle starts in any automata (sequence of connected nodes) and not necessarily only a singly linked list. Consider the automata given below, which has a cycle of length n and the node where the cycle starts is at a distance m from the start.

It can be proved that if we move the slow and fast pointers at different speeds, they meet at some node in the cycle. This is because, after m iterations when slow pointer reaches the node b, the fast pointer will have traversed a distance 2*m and so will be at some node c such that the distance between the node b and c is k = m % n.

From here on, the slow and fast pointers go around in the cycle but at different speeds. In each iteration, the gap k between slow and fast increases by one, but since it is a cycle, the gap between fast and slow i.e. n-k decreases by one, and so after n-k iterations fast and slow both point to the same node d that is at a distance x from the node b such that x = n - k

To find where the cycle starts (node b), we move the fast pointer back to the head and move both fast and slow pointer 1 step at a time (at the same speed). It is guaranteed that they will eventually meet at node b. This is because after m iterations, fast will reach node b, and slow will be at a distance (x + m) % n from node b. Expanding equations as given below, it can be proved that (x + m) % n equals 0,

Based on the above, after m iterations the fast pointer will be at a distance (x + m) % n from node b but since (x + m) % n = 0 it means it will be at the node b where it will meet the slow pointer.

We can see, as above, why Floyd's cycle finding algorithm always correctly finds the cycle and the node where it starts.

Complexity Analysis

The algorithm uses the fast and slow pointer technique to traverse the list. As stated in the proof of correctness, the fast and slow pointers meets after a fixed number of iterations, so the worst-case time complexity is linear O(N).

We don't create additional data structures to traverse both arrays, so the space complexity is constant O(1).

Best Case

• Space Complexity - O(1)
• Time Complexity - O(N)

Worst Case

• Space Complexity - O(1)
• Time Complexity - O(N)

Example problems

Most problems in this category are easy or medium and can be solved by directly applying Floyd's cycle-finding algorithm. Below is a list of a few problems.

• Detect cycle - Detect if a linked list has a cycle.
• Remove loop - If a linked list has a cycle, remove it

We will now solve these problems to understand Floyd's cycle-finding algorithm better.