Identifying the fast and slow pointer pattern
The fast and slow pointer technique can only be applied to some specific problems. These are generally easy or medium problems where we must find a node at a proportional distance between two nodes. Most often these problems are about finding the middle node of a segment or the middle node of the entire list. If the problem statement or its solution follows the generic template below, it can be solved by applying the sliding window traversal technique.
Given a linked list and two nodes
start and end at a distance of L from each other, find the node at a distance of x from start and n*x from end such that n > 0 and L % n == 0.Example
Let's consider the following problem as an example to better understand how to identify and solve a problem using the fast and slow pointer technique
Problem statement: Given a linked list, find the middle node.
Find the middle node of a linked list
Fast and slow pointer solution
The problem description directly fits the generic template for the fast and slow pointer traversal pattern we learned earlier.
start (head) and end (last node) find the node at a distance of x from start and n*x from end where n = 1We initialize two references slow and fast with the head node and iterate using fast until we reach the last node (either null or node before null) of the list. In each iteration, we move slow n (1) step ahead and fast n+1 (2) steps ahead. At the end of all iterations, slow holds the reference to the node at the middle of the given list.
For linked lists that have an odd number of nodes, the traversal will terminate when fast reaches the last node and slow points to the node in the middle of the list. For a list with an even number of nodes, no (middle) node is equidistant from both ends, as the real middle of the list lies between two nodes. In this case, the traversal will terminate when fast hits null and slow points to the "second" middle node.
Fast the middle node of a the linked list
The implementation of the fast and slow pointer solution is given as follows.
C++
Java
Typescript
Javascript
Python
As the code above demonstrates, we can find the middle node of the given list using the fast and slow pointer technique in a single pass.
Example problems
Most problems that fall under this category are easy problems; a list of a few is given below.
We will now solve these problems to understand the fast and slow pointer technique better.