Understanding the fast and slow pointer pattern

We can easily find the middle item in the array by dividing its length by two and accessing it using its index. However, unlike arrays, singly linked lists don't have a fixed size, and we cannot randomly access items using indices. Finding the middle node in the list requires two passes, first to find the length of the list and second to find the node at half the length from the start.

The problem can be further extended to find a node between two given nodes at a proportional distance from both. The fast and slow pointer technique can find that node in a single pass.

The fast and slow pointer pattern is a classification of problems that can be solved using the fast and slow pointer technique.
Loading Image

The fast and slow pointer technique can be used to find a node at a proportional distance from two ends.

Fast and slow pointer technique

Consider we are given a singly linked list and two nodes start and end, and we need to find a node that is at a distance x from start and n*x from end. It is guaranteed that a solution node exists.

It should be noted that a solution node will only exist if the length L between start and end is a multiple of n i.e, L % n == 0

The idea is to initialize two references flast and slow with start and move them forward at different speeds until fast reaches end.The slow reference moves 1 step in each iteration, while the fast reference moves (n+1) steps. This way, at the end of every iteration, the slow reference is at a proportional distance from the start and fast reference. When the fast reference reaches end, the slow reference points to the solution node.

Most problems require finding the middle node between two nodes, i.e. where n=1
Loading Player

1 of 14

Fast and slow pointer traversal by a factor of n

Algorithm

The algorithm given below outlines the fast and slow pointer traversal technique for a linked list of size n.

  • Step 1: Initialize two references, `slow` and `fast` with the head of the list.
  • Step 2: Loop while `fast.next` != `null` and `fast` != `end` and do the following
    • Step 2.1: Move slow 1 step ahead by setting `slow` = `slow.next`
    • Step 2.2: Move `fast` `n+1` times setting `fast` = `fast.next` `n+1` times.
  • Step 3: Node held in `slow` is the solution node

Implementation

Given below is the generic code implementation of the fast and slow pointer traversal technique on a linked list.

  1. C++

  2. Java

  3. Typescript

  4. Javascript

  5. Python

Complexity Analysis

The algorithm's time and space complexity is easy to understand. In the worst case, the start and end are the first and the last node in the list, and the fast reference traverses from the start to end of the list, which has a linear O(N) runtime complexity where N is the length of the linked list. In the best case, start and end may only have one node in between and n=1. In this case, the fast reference only traverses two nodes, and the runtime complexity would be constant O(1).

Since we do not create a new data structure, the space complexity is constant O(1). 

Best Case

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

Worst Case

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

Later in the course, we will examine techniques for identifying problems that can be solved using the fast and slow pointer technique and walk through an example to better understand it.

Prev ModuleNext
Login to save progress