Fast and Slow Pointer: Floyd’s Cycle Detection Algorithm

Fast and Slow Pointer: Floyd’s Cycle Detection Algorithm
49views

Leetcode Problem: Linked List Cycle

Source

While going about my algorithm practice, I came across an interesting concept that I definitely wish I had seen earlier. I knew about pointers, and how having two pointers can sometimes help you solve a problem; basically keeping track of where you are in a linked list, or array, or graph but at two different locations. However, I had only ever used them to start at different parts of the data structure, or by keeping one static while one of them moved. I have never considered moving them at different speeds! That's when I discovered fast and slow pointers and it has now opened up a whole world of possibilities.

Fast and Slow Pointer

The fast and slow pointer technique (also known as the tortoise and hare algorithm) uses two pointers to determine traits about directional data structures. This can be an array, singly-linked list, or a graph. It is often applied to determine if there are any cycles in the data structure and is therefore also known as Floyd’s Cycle Detection Algorithm.

To implement this algorithm, the two pointers will start at a location (the head node in the case of determining cycles in a linked list). Then, with each iteration, the two pointers will be advanced at different rates. Usually, the slow pointer will move ahead one step while the fast pointer moves ahead two. Though they are free to move at any rate as long as the rates are different.

Now for detecting a cyclic list, sooner or later, both pointers will meet at the same node. If they never meet then there is no cycle. This is because the distance between the two pointers increases by a set amount after every iteration. When the distance becomes the same as the length of the list, they meet because they are moving in a cycle.

Intuitive Proof

The proof of this algorithm involves some math. However, it is easier to understand the algorithm intuitively. Imagine two runners on a track. They run at different speeds but they start at the same location. If the track is not cyclic in any way, then the slow runner will never meet the fast runner, as they will always be ahead of them. However, if the track is cyclic, the fast runner will eventually “lap” the slow runner, or catch up to him and pass him.

Here is a more in-depth proof of the algorithm

Example Implementation

Here's how to use this algorithm for the Leetcode problem: Linked List Cycle. Given the head of a linked list, determine if the linked list has a cycle in it. There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer (see image below).

Source: Linked List Cycle (LeetCode)

We can use the fast and slow pointers as discussed above. If there is a loop, they will, at some point, meet each other and we can return true. However, if the fast pointer reaches an end before joining up with the slow pointer, we know there was no cycle and we return false.

The final code:

function hasCycle(head) {
let fast = head
let slow = head
while (fast && fast.next) {
fast = fast.next.next
slow = slow.next
if (fast == slow) return true
}
return false
}

Space-Time Complexity:

The space complexity in the above algorithm is constant (O(1)). We only additionally store two nodes of the linked list to determine where the fast or slow pointer is.

Now the time complexity is a little harder to understand. For the above algorithm, the runtime complexity is linear (O(n)). In detecting the cycle, depending on where the cycle occurs, the fast and slow pointers may not meet on the first iteration through the linked list. But it will catch it after a certain constant number of cycles, let's call it k cycles. Therefore the runtime is k * O(n) which results in the linear runtime complexity.

Another way to think about it is that even though the fast pointer is moving twice as fast as the slow pointer, if we look at it from the frame of reference of the slow pointer, essentially, the slow pointer is static and the fast one is moving 1 step at a time.

This StackOverflow question goes into the proof of the runtime complexity of the algorithm.

Implementation 2

Here's another implementation of this fast and slow pointer technique. Consider the LeetCode problem: Middle of the Linked List. Given a non-empty, singly linked list, return a middle node of the linked list. If there are two middle nodes, return the second middle node.

We can take advantage of two pointers moving at different rates here. If we set the fast pointer to be twice as fast as the slow one, then when the fast pointer reaches the end of the linked list, the slow pointer will have only made it half the distance. Which means it will be at the middle node! Take a look at the image below:

Source: AfterAcademy

The final code:

function middleNode(head) {
let fast = head
let slow = head
while (fast && fast.next) {
fast = fast.next.next
slow = slow.next
}
return slow
}

Additional Problems

Now that we have this new tool in our toolbox, let's see what else we can do with it. The following LeetCode problems can also be solved using this fast and slow pointer technique:

References


Fast and Slow Pointer: Floyd’s Cycle Detection Algorithm was originally published in codeburst on Medium, where people are continuing the conversation by highlighting and responding to this story.

Leave a Response

Solve : *
14 × 29 =


%d bloggers like this: