← All posts

Algorithms / Fast and Slow Pointers For Linked List

In a Linked List, traversal is restricted to forward only, you can’t really go back to previous nodes once you go past them. When working on a problem that requires us to do some lookup in a Linked List, the naive approach is to traverse the list multiple times.

Another better approach is to use the Fast and Slow Pointers technique. Most of the time, we can solve the problem with a single pass.

Let’s take a look at some example use cases.

Find the $n^{th}$ node from the end of the list

Let’s say, we want to find the $n^{th}$ node from the end of a Linked List, we can do it naively by traversing from the head to the tail to get the length $L$ of the list, then do a second traversal just $L - n$ times.

Using fast and slow pointers, we can first increase the fast pointer n times, the distance between fast and slow is now n nodes.

Now, increase both the fast and slow pointers until fast reaches the end of the list. Since the two pointers have the distance of n, the position of the slow pointer is the $n^{th}$ node from the end of the list.

The algorithm can be implemented like this:

fast := head
slow := head
 
for n > 0 {
    fast = fast.Next
}
 
for fast.Next != nil {
    fast = fast.Next
    slow = slow.Next
}
 
// slow is the nth from the end here

Find the middle node of the list

Another example, this time we want to look for the middle node of the list. We can do it naively by traversal the list in two-pass, with the second pass in $L/2$ times.

Using fast and slow pointers, we increase the slow pointer one node at a time, and the fast pointer goes twice as fast with fast = slow.Next.Next, by the time fast reaches the end of the list, the slow pointer will be in the middle:

Implementation:

fast := head
slow := head
 
for fast != nil && fast.Next != nil {
    slow = slow.Next
    fast = fast.Next.Next
}
 
// end of the loop, slow is the middle node

A similar technique can also be applied to detect a cycled linked list. Since the fast pointer will always, at some point, meet the slow pointer if it keeps cycling.

---