Master Coding Interviews : Part 3 ( Fast & Slow Pointers Pattern )

#coding #algorithms #interview #webdev

In Part 1 we saw how a sliding window collapses a nested loop into a single pass over an array. In Part 2 we used two pointers moving toward each other — or side by side — to restructure and search sorted arrays in O(n) time and O(1) space.

Today's pattern shares that same O(1) space philosophy, but it lives in a different world: linked lists. Meet the Fast & Slow Pointers pattern — also known as Floyd's Cycle Detection Algorithm.

What is the Fast & Slow Pointers Pattern?

The concept comes from a simple real-world intuition: imagine two runners on a circular track. One runs twice as fast as the other. If the track loops back on itself, the fast runner will eventually lap the slower one — they are guaranteed to meet. If the track is a straight line with a finish line, the fast runner simply gets there first and stops.

We apply exactly this logic to linked lists:

The slow pointer advances one node at a time
The fast pointer advances two nodes at a time
If the list has a cycle, they will eventually collide inside it
If the list has no cycle, the fast pointer hits the end (null) and we stop

This pattern is remarkably versatile: it detects cycles, finds the middle of a list, and even identifies the entry point of a cycle — all without any extra data structures.

Problem 1 — Linked List Cycle

Given the head of a singly linked list, determine if the linked list has a cycle in it or not. Return True if there is a cycle, False otherwise.

Example:

Input: head = [3, 2, 0, -4] where the tail connects back to the node at index 1
Output: True

The most natural solution that comes to mind is to keep track of every node we visit using a hash set. If we ever encounter a node we've seen before, we know there's a cycle.

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        visited = set()
        current = head

        while current:
            if current in visited:
                return True   # We've seen this node before — cycle detected
            visited.add(current)
            current = current.next

        return False  # Reached the end of the list — no cycle

This solution works correctly, but it comes with a cost we can't ignore:

Space complexity : O(n) : We store a reference to every visited node in the hash set — for a linked list with a million nodes, that's a million references sitting in memory.
In memory-constrained environments — embedded systems, low-resource servers, or simply very large linked lists — allocating that extra data structure is not always acceptable.
The problem itself hints at a better path: can you solve it using O(1) memory ?

Optimization through the Fast & Slow Pointers Pattern

Here's where Floyd's algorithm shines. We replace the hash set entirely with just two pointers — and get O(1) space as a result.

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        slow = head   # Tortoise: moves one step at a time
        fast = head   # Hare: moves two steps at a time

        while fast and fast.next:
            slow = slow.next          # Tortoise takes one step
            fast = fast.next.next     # Hare takes two steps

            # If the pointers meet, the hare has lapped the tortoise
            # — a cycle exists
            if slow == fast:
                return True

        # Fast pointer reached the end of the list — no cycle
        return False

Time complexity : O(n) — in the worst case, the fast pointer traverses the list once.

Space complexity : O(1) — two pointers, no auxiliary data structure.

Why does it work ? If a cycle exists, the fast pointer enters it and begins "lapping" the slow pointer. Each iteration, the gap between them shrinks by exactly one step. Since the gap is finite and decreases by one per iteration, they are mathematically guaranteed to meet. If there is no cycle, the fast pointer reaches null and the loop exits cleanly.

Problem 2 — Middle of the Linked List

Given the head of a singly linked list, return the middle node of the linked list. If there are two middle nodes, return the second middle node.

Example:

Input: head = [1, 2, 3, 4, 5]
Output: Node with value 3

The straightforward solution is to count all nodes in a first pass, then walk to the midpoint in a second pass.

class Solution:
    def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
        length = 0
        current = head

        # First pass: count all nodes
        while current:
            length += 1
            current = current.next

        # Second pass: walk to the middle
        middle = length // 2
        current = head
        for _ in range(middle):
            current = current.next

        return current

This is perfectly correct, and it does run in O(n) time — but it makes two full passes over the list and requires you to know the total length before you can find the middle. Can we find the middle in a single pass, without knowing the length upfront ?

Optimization: Finding the Middle in One Pass

This is where the Fast & Slow Pointers pattern reveals a second superpower. Since the fast pointer moves at twice the speed of the slow pointer, by the time the fast pointer reaches the end of the list, the slow pointer will have traveled exactly half the distance — landing precisely at the middle.

class Solution:
    def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
        slow = head   # Will reach the middle when fast reaches the end
        fast = head   # Moves twice as fast as slow

        while fast and fast.next:
            slow = slow.next          # One step
            fast = fast.next.next     # Two steps

        # When fast is at the end, slow is at the middle
        return slow

Time complexity : O(n) — a single pass through the list.

Space complexity : O(1) — no extra memory allocated.

The two-pass approach and this one-pass approach share the same time complexity on paper, but the single-pass version is cleaner and more elegant — and it demonstrates a deep understanding of the pattern that interviewers notice.

When to use this pattern

When dealing with linked lists where you need to detect or reason about cycles
When you need to find the middle of a linked list in a single pass
When the problem asks for O(1) space on a linked list problem — this is almost always the signal
When the brute-force solution uses a hash set to track visited nodes — that extra space is almost always replaceable with fast & slow pointers
When the problem involves cyclic sequences, repeated states, or asks for the entry point of a cycle

What's next ? Practice

Head over to LeetCode and explore the linked list problem set. A few great next problems to challenge yourself with this pattern:

Linked List Cycle II (Medium) — can you find the exact node where the cycle begins ?
Happy Number (Easy) — fast & slow pointers applied to a numeric sequence, not a list
Reorder List (Medium) — combines middle-finding with a reversal

PS: Not every linked list problem requires this pattern, and Floyd's algorithm isn't the only way to detect a cycle. Keep building your instinct for when a pattern fits — that recognition is the real skill interviewers are testing.

See you in the next article for another coding pattern !