Fast and Slow Pointers in Linked Lists

1. The Core Concept: Hare and Tortoise

The idea is simple yet brilliant. We use two pointers, but instead of moving them towards each other, they both start at the beginning of the data structure and move in the same direction, but at different speeds.

• A slow pointer moves one step at a time (slow = slow.next).
• A fast pointer moves two steps at a time (fast = fast.next.next).

This relative speed difference is the key to unlocking solutions for several tricky linked list problems. Let's start with a short video that introduces the fundamental concept.

2. Application 1: Finding the Middle of a Linked List

A common interview question is to find the middle node of a singly linked list in a single pass.

The Problem: Given the head of a singly linked list, return the middle node. If there are two middle nodes (in an even-length list), return the second one.

A naive approach would be to traverse the list once to find its length (n), then traverse it a second time up to n/2 to find the middle node. This works, but it requires two passes. The fast and slow pointer technique elegantly solves this in a single pass.

The Logic:
By the time the fast pointer reaches the end of the list, the slow pointer will be exactly at the midpoint. Think about it: the slow pointer travels half the distance of the fast pointer.

For a detailed walkthrough of this logic, including how it handles both odd and even length lists and a code implementation, let's return to the Destination FAANG video.

The Python implementation is concise and demonstrates the pattern's elegance:

def middleNode(self, head):
    slow = head
    fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    return slow

3. Application 2: Detecting a Cycle in a Linked List

This is the classic problem for which this pattern was originally popularized, known as Floyd's Cycle-Finding Algorithm.

The Problem: Given the head of a linked list, determine if it has a cycle. A cycle exists if some node in the list can be reached again by continuously following the next pointer.

A common first thought is to use a hash set to store each node as you traverse the list. If you encounter a node that's already in the set, you've found a cycle. This works, but your interviewer will almost certainly follow up with: "Can you do it in O(1) space?"

This is where the fast and slow pointers shine.

The Logic:

1. Initialize slow and fast pointers at the head.
2. Move them at their respective speeds.
3. If the linked list has a cycle, the fast pointer will enter the cycle first, followed by the slow pointer. Eventually, the fast pointer will "lap" the slow pointer, and they will meet at the same node.
4. If the linked list does not have a cycle, the fast pointer (or fast.next) will reach null.

Why is a meeting guaranteed?

It's crucial to understand why they are guaranteed to meet. Once both pointers are inside the cycle, the fast pointer gains one position on the slow pointer with every iteration. Imagine two runners on a circular track; the faster runner will inevitably lap the slower one.

For a rigorous but intuitive explanation of this, the NeetCode channel provides one of the best breakdowns.

Implementation

Now that you understand the what and the why, let's look at a full walkthrough that contrasts the hash set approach with the optimal one and provides a clean implementation.

Conclusion

You've now added a second major two-pointer pattern to your toolkit. While the converging pointer pattern is your go-to for sorted arrays, the fast and slow pointer pattern is the key to optimally solving many linked list problems.

Key Takeaways:

• The Fast and Slow Pointer (Hare and Tortoise) technique uses two pointers moving at different speeds (usually 1x and 2x) through a sequence.
• It finds the middle of a linked list in a single pass, as the slow pointer will be at the midpoint when the fast pointer reaches the end.
• It detects cycles in O(1) space by guaranteeing that the fast pointer will eventually lap and meet the slow pointer if a cycle exists. This O(1) space complexity is its main advantage over a hash set solution.

The article Fast & Slow Pointers: Master Floyd's Cycle Detection provides a concise summary and some excellent interview tips in the section "Interview Tips & Tricks" (resource ID LINK, section 5) which are worth reviewing as you practice.

In our next lesson, we will continue building our linked list manipulation skills by tackling another fundamental interview problem: reversing a linked list iteratively using pointers.