Algorithm Patterns 101: Fast and Slow Pointers

Similar to two pointers, fast and slow pointers use two pointers to traverse data structures.

But this comes with one key difference, the pointers iterate at different speeds. The pointers can be used to traverse the array or list in either direct, BUT one must move faster than the other.

But how does one move faster? The slow pointer moves forward by one and the fast pointer moves be a factor of two.

• Fast and slow pointers are used to determine structural traits
• The key idea is that pointers start at the same location, but they move forward
• If the fast pointer “catches” the other pointer, there is a cycle.

Linked List Cycle w/ Fast & Slow Pointers

Linked List cycles are by far the most common scenario where Fast and Slow pointers are used.

public boolean detectCycle(Node head) {
    if(head == null) {
        return false;
    }

    Node slow = head, fast = head.next;
    while(slow != fast) {
        if(fast == null || fast.next == null) {
            return false;
        }
        slow = slow.next;
        fast = fast.next.next;
    }
    return true;
}

• Check if first node is empty (this is a clean code convention called “fail first”)
• Initialize the slow and fast pointers
• Iterate until the function returns false OR the places in memory equal each other

Middle of Linked List w/ Fast & Slow Pointers

Unlike arrays, we can’t just pull data out out of linked-list without traversing. This is where the power of fast and slow pointers really shines. The idea is to traverse the linked list at different rates.

public Node middleNodeOfList(Node head) {
    Node slow = head, fast = head;

    // iterate until fast or null
    while(fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }

    return slow;
}

• First, we must initialize our fast and slow pointers
• Next, iterate until the fast pointer reaches the end
• Once this occurs our slow pointer will be pointing to the middle element.

If this is confusing, remember the key idea is that the fast pointer is moving double the speed of the other pointer.