Two Pointers × Linked List Problems: Fast and Slow Pointers

Example problems for this article:

• LeetCode 876 - Middle of the Linked List (Easy) — Finding the middle of a linked list
• LeetCode 19 - Remove Nth Node From End of List (Medium) — Finding the k-th element from the end of a linked list
• LeetCode 141 - Linked List Cycle (Easy) — Detecting whether a cycle exists in a linked list

In the previous article, we analyzed the classic Two Sum II problem and the two pointers technique. The term “two pointers” appears in many problem solutions — so what other problems can be solved using two pointers?

In practice, “two pointers” is a very broad concept. Any approach that uses two pointers (whether linked list pointers or array indices) can be called a two-pointer method. Depending on how the two pointers move, the technique can be categorized into same-direction pointers, opposite-direction pointers, fast and slow pointers, and so on.

When the two-pointer technique meets linked list problems, we primarily use the fast and slow pointers approach. Many times when you encounter tricky linked list operations, fast and slow pointers can help reduce the time or space required by the algorithm.

This article will cover:

• Characteristics of fast and slow pointers in linked list problems
• Case studies of fast and slow pointers: finding the middle of a linked list, finding the k-th element from the end
• A classic problem using fast and slow pointers: detecting a cycle in a linked list
• Related problems

Two Pointers in Linked List Problems

As we know, the nature of the linked list data structure means it can only be traversed sequentially in one direction — it does not support reverse traversal or random access (access by index). Many times, we need the fast and slow pointer technique to achieve a degree of reverse traversal, or to reduce the number of passes through the list. That is why fast and slow pointers are so commonly used in linked list problems.

Fast and slow pointers in linked list problems can be further divided into several different types. Below we will walk through three application scenarios of fast and slow pointers.

Example 1: Finding the Middle of a Linked List

LeetCode 876 - Middle of the Linked List (Easy)

The conventional approach to finding the middle of a linked list is to first traverse the entire list to compute its length $n$, then traverse it again to find the $n/2$-th element. This requires two passes through the list.

A more elegant approach uses two pointers — one fast and one slow. The fast pointer advances two nodes at a time, moving at twice the speed of the slow pointer. When the fast pointer reaches the end of the list, the slow pointer is right at the middle. The process is shown in the animation below. This way, we only need a single pass. Of course, the time complexity is still $O(n)$, but for linked list problems, this kind of trick to eliminate one extra pass is exactly what we need.

The solution code is shown below. Note that the loop condition is fast != null && fast.next != null to prevent null pointer exceptions.

public ListNode middleNode(ListNode head) {
    ListNode fast = head;
    ListNode slow = head;
    while (fast != null && fast.next != null) {
        // fast advances two elements at a time, slow advances one
        fast = fast.next.next;
        slow = slow.next;
    }
    // When the list has an odd number of elements, slow points to the middle
    // When the list has an even number of elements, slow points to the right one of the two middle nodes
    return slow;
}

Example 2: Finding the K-th Element from the End of a Linked List

LeetCode 19 - Remove Nth Node From End of List (Medium)

The conventional approach to finding the $k$-th element from the end of a linked list is to first traverse the list to compute its length $n$. Then we can calculate that we need the $(n-k)$-th element, and traverse the list once more.

Here again, we can use the fast and slow pointer technique to eliminate one pass. This time, the two pointers move at the same speed but are separated by a fixed distance. The fast pointer advances $k$ elements first, and then both pointers move forward at the same speed. When the fast pointer reaches the end of the list, the slow pointer is exactly at the $k$-th element from the end. The animation below shows the advancing process (using $k=3$ as an example).

The solution code is shown below. Note that the problem requires not only finding the k-th element from the end but also removing it. To delete the element, we need to use the linked list traversal framework from the first lecture, splitting the slow pointer into prev and curr pointers. (For the specific usage of prev and curr pointers, please review the first lecture on your own.) So here we actually have three pointers advancing together — pay attention to the relationships between them.

public ListNode removeNthFromEnd(ListNode head, int k) {
    // Advance fast by k elements
    ListNode fast = head;
    for (int i = 0; i < k; i++) {
        // Null pointer checking code is omitted here
        fast = fast.next;
    }
    // fast and slow pointers advance simultaneously with a gap of k
    // Here we use the linked list traversal framework, splitting slow into two pointers: curr and prev
    ListNode curr = head;
    ListNode prev = null;
    while (fast != null) {
        prev = curr;
        curr = curr.next;
        fast = fast.next;
    }
    if (prev == null) {
        head = curr.next;
    } else {
        prev.next = curr.next;
    }
    return head;
}

The problem assumes that the value of k is always valid, so several validity checks are omitted from the code. However, in an interview, we should consider cases where the input $k$ is invalid to ensure the robustness of the program.

Example 3: Detecting Whether a Cycle Exists in a Linked List

LeetCode 141 - Linked List Cycle (Easy)

This problem features a slight variation on linked lists. The tail node of the list might point to some node within the list, forming a cycle, as shown in the figure below.

We need to determine whether a linked list is a regular list or one with a cycle. If we only use a single pointer for traversal, it is actually quite difficult to detect the presence of a cycle — we would have to use a set to store all previously visited nodes. But with fast and slow pointers, we can do it without any extra space.

We let the fast pointer advance two nodes at a time and the slow pointer advance one node at a time. Once both pointers enter the cycle, the fast pointer will “lap” the slow pointer, catching up to it from behind. The catching-up process is shown in the animation below.

If there is no cycle in the list, the fast pointer will never point to the same node as the slow pointer — instead, it will reach the end of the list. Based on this idea, we get the following solution code.

public boolean hasCycle(ListNode head) {
    ListNode fast = head;
    ListNode slow = head;
    while (fast != null && fast.next != null) {
        fast = fast.next.next;
        slow = slow.next;
        // fast and slow point to the same node, meaning a "lap" has occurred
        if (fast == slow) {
            return true;
        }
    }
    // fast reached the end of the list, so there is no cycle
    return false;
}

There is also a follow-up question, LeetCode 142 - Linked List Cycle II, which asks you to find the first node where the cycle begins. This also requires fast and slow pointers and involves some mathematical proof. I won’t go into detail on this one here — interested readers can try solving it on their own.

Summary

This article covered “fast and slow pointers,” a category within the two-pointer technique, used to solve linked list problems. Fast and slow pointers have several variations, all of which were demonstrated in this article.

Linked list problems are not complex. The linked list traversal framework from the first lecture and the fast and slow pointers covered in this article are the two most important techniques for linked list problems. With enough practice, linked list problems become very easy.

Finally, here is a comprehensive practice problem on linked lists: Sort List (LeetCode 148 - Sort List). This problem requires various linked list handling techniques and demands choosing an appropriate sorting algorithm based on the properties of linked lists. One could say that mastering this problem means mastering linked list problems in general. Sort List is also one of a certain Microsoft interviewer’s go-to questions, which speaks to its universality.

In the previous lecture and this one, we explored two different types of two-pointer methods: opposite-direction pointers and fast and slow pointers. There is yet another classic type of two-pointer technique — the sliding window — which will be covered in a later chapter. Stay tuned.