Fast and Slow Pointers (Tortoise & Hare)

Concept

If you want to find the exact middle of an Array, you just do Math.floor(array.length / 2) in $O(1)$ time.
In a Singly Linked List, you don’t know the length. The only way to find the middle is to traverse the entire list to count the nodes ($O(N)$), divide the count by 2, and then traverse the list again to reach the middle ($O(N/2)$).

The Fast and Slow Pointers technique allows you to find the middle (or detect loops) in a single pass.

Finding the Middle Node

You initialize two pointers at the Head: Slow and Fast.

• The Slow pointer moves 1 step at a time.
• The Fast pointer moves 2 steps at a time.

When the Fast pointer physically hits the end of the list (null), the Slow pointer will be sitting exactly on the middle node.

function middleNode(head: ListNode | null): ListNode | null {
    let slow = head;
    let fast = head;

    // Keep going as long as Fast has 2 valid steps ahead of it
    while (fast !== null && fast.next !== null) {
        slow = slow!.next;        // +1
        fast = fast.next.next;    // +2
    }

    // Fast hit the end. Slow is in the middle.
    return slow;
}

Cycle Detection (Floyd’s Algorithm)

The most famous application of this technique is detecting if a Linked List has a Cycle (a node’s next pointer accidentally points backward to a previous node, creating an infinite loop).

If there is no cycle, Fast hits null and the program ends safely.
If there is a cycle, Fast will loop around the circle infinitely. Eventually, the Slow pointer will enter the circle.
Because Fast moves exactly 1 step faster than Slow relative to each other, Fast will inevitably lap Slow and they will physically collide on the exact same node.

function hasCycle(head: ListNode | null): boolean {
    let slow = head;
    let fast = head;

    while (fast !== null && fast.next !== null) {
        slow = slow!.next;
        fast = fast.next.next;

        // They collided! There is a cycle.
        if (slow === fast) {
            return true;
        }
    }

    return false;
}

Interview Questions

Q: A developer tries to detect a cycle by using a Set. They traverse the list, adding every node’s memory address to the Set. If they encounter a node that already exists in the Set, they return true. Is this a valid solution?
A: Yes, this is an entirely valid and highly readable solution.
However, it has an algorithmic flaw. Storing the nodes in a Set requires $O(N)$ Space Complexity. If the Linked List has 10 million nodes, you will consume massive amounts of RAM.
Floyd’s “Tortoise and Hare” algorithm only requires two variables (slow and fast), achieving the exact same result with mathematically perfect $O(1)$ Space Complexity. If an interviewer asks you to solve it in $O(1)$ space, you must use the Two Pointer technique.

Q: You are asked to determine if a Linked List is a Palindrome (e.g., 1 -> 2 -> 2 -> 1). How do you use Fast and Slow pointers to solve this in $O(1)$ space?
A: This is a beautiful combination of multiple Linked List techniques!

1. Use Fast and Slow pointers to find the exact middle of the list.
2. Sever the list in half. Use the Reverse a Linked List algorithm to physically reverse the second half of the list (so it becomes 1 -> 2).
3. Place one pointer at the Head of the first half, and another pointer at the Head of the reversed second half.
4. Step them forward one by one. If all values match, it is a Palindrome.
   (All of this pointer manipulation requires $O(1)$ extra space!).