Fast and Slow Pointers

The fast and slow pointers technique (also called the tortoise and hare algorithm) uses two pointers that move through a sequence at different speeds to detect cycles, find midpoints, and solve problems that would otherwise need extra memory to track visited state. It shows up constantly in linked list problems, and in any problem where a sequence of values can loop back on itself, such as detecting a repeating pattern in a number sequence. Mastering it lets you solve a whole class of interview questions in O(n) time using only O(1) extra space, without ever building a hash set of visited nodes.

Overview: How It Works

Picture two runners on a track: a tortoise that takes one step at a time and a hare that takes two steps at a time. If the track is a straight line with an end, the hare simply reaches the end first. But if the track loops back on itself, the hare will eventually lap the tortoise and the two will land on the exact same spot again. That collision is proof a loop exists, and it is the entire idea behind the fast and slow pointers technique.

In code, this means keeping two references (usually named slow and fast) that both start at the beginning of a linked list, or more generally at the start of any next-state sequence. On every iteration, slow advances one step (slow = slow.next) while fast advances two steps (fast = fast.next.next). Three things can happen:

• If the list has no cycle, fast reaches the end (None) first, and the loop stops safely.
• If the list has a cycle, fast enters the loop before slow does, keeps circling inside it, and because it is gaining exactly one extra step on slow every iteration, it is guaranteed to eventually land on the same node as slow.
• If we only care about the midpoint and there is no cycle, then by the time fast reaches the end, slow has covered exactly half the distance, because it moved at half the speed.

Why the hare always catches the tortoise

Think about the gap between fast and slow once both are inside the cycle. Each iteration, fast closes the gap by exactly one node, since it gains two steps while slow gains one, a net gain of one. A gap that shrinks by one every step and wraps around a cycle of finite length must eventually hit zero, since it decreases by exactly one each time and cannot skip over zero. That is why the meeting is guaranteed, no matter how long the cycle is.

The same different-speeds idea generalizes beyond linked lists. Any process you can describe as start at some state, then repeatedly apply a function to reach the next state, is fair game: a number transforming into the sum of the squares of its digits (the happy number problem), a sequence of array indices where arr[i] points to the next index, and duplicate-finding in an array all reduce to the same slow and fast walk.

Time and Space Complexity

Let n be the number of nodes in the list, or the number of states before a cycle repeats in a general sequence.

Operation	Time	Space	Why
Find the middle node	O(n)	O(1)	fast traverses the list once at double speed while slow tags along, so total work is proportional to n, using only two pointer variables.
Detect a cycle	O(n)	O(1)	With no cycle, fast reaches the end within about n/2 iterations. With a cycle, the gap between the pointers shrinks by one each step once both are inside the loop, so they meet within the cycle’s length, still bounded by n.
Find where the cycle starts	O(n)	O(1)	Same bound as detection, plus a second phase that walks two single-speed pointers from the head and the meeting point until they align, also O(n).

Compare this to the naive alternative for cycle detection: storing every visited node in a set and checking membership as you go. That approach is also O(n) time, but it costs O(n) extra space for the set. The fast and slow pointer trick achieves the same time complexity with constant space, which is precisely why it is the expected answer in interviews.

Examples

Example 1: Finding the Middle of a Linked List

This example builds a seven-node linked list and uses the classic slow and fast loop to land on its middle node.

class ListNode:
    def __init__(self, val: int, next: "ListNode | None" = None) -> None:
        self.val = val
        self.next = next

def find_middle(head: ListNode) -> ListNode:
    slow = head
    fast = head
    while fast is not None and fast.next is not None:
        slow = slow.next
        fast = fast.next.next
    return slow

def build_linked_list(values: list[int]) -> ListNode:
    head = ListNode(values[0])
    current = head
    for val in values[1:]:
        current.next = ListNode(val)
        current = current.next
    return head

def print_from(node: "ListNode | None") -> None:
    values = []
    while node is not None:
        values.append(str(node.val))
        node = node.next
    print(" -> ".join(values))

if __name__ == "__main__":
    head = build_linked_list([1, 2, 3, 4, 5, 6, 7])
    middle = find_middle(head)
    print(f"Middle node value: {middle.val}")
    print_from(middle)

Output:

Middle node value: 4
4 -> 5 -> 6 -> 7

The list holds seven nodes with values 1 through 7. Both pointers start at the head (value 1). Each loop iteration moves slow one node and fast two nodes, as long as fast and fast.next are both not None. After three body executions, fast lands on the last node (7) with nothing after it, so the loop stops, and slow has landed on node 4, the exact middle of an odd-length list. For an even-length list this same loop lands slow on the second of the two middle nodes.

Example 2: Detecting a Cycle and Locating Its Start

This example builds a list whose tail is wired back into an earlier node to form a cycle, then detects the cycle and finds exactly where it begins.

class ListNode:
    def __init__(self, val: int, next: "ListNode | None" = None) -> None:
        self.val = val
        self.next = next

def has_cycle(head: "ListNode | None") -> bool:
    slow = head
    fast = head
    while fast is not None and fast.next is not None:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            return True
    return False

def find_cycle_start(head: "ListNode | None") -> "ListNode | None":
    slow = head
    fast = head
    found_cycle = False
    while fast is not None and fast.next is not None:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            found_cycle = True
            break
    if not found_cycle:
        return None
    pointer = head
    while pointer is not slow:
        pointer = pointer.next
        slow = slow.next
    return pointer

def build_cyclic_list(values: list[int], cycle_index: int) -> ListNode:
    head = ListNode(values[0])
    current = head
    nodes = [head]
    for val in values[1:]:
        current.next = ListNode(val)
        current = current.next
        nodes.append(current)
    if cycle_index >= 0:
        current.next = nodes[cycle_index]
    return head

if __name__ == "__main__":
    cyclic_head = build_cyclic_list([3, 2, 0, -4], 1)
    print(f"Has cycle: {has_cycle(cyclic_head)}")
    start = find_cycle_start(cyclic_head)
    print(f"Cycle starts at node with value: {start.val}")

    acyclic_head = build_cyclic_list([1, 2, 3], -1)
    print(f"Has cycle: {has_cycle(acyclic_head)}")

Output:

Has cycle: True
Cycle starts at node with value: 2
Has cycle: False

The first list is [3, 2, 0, -4] with the last node’s next pointer rewired back to index 1 (the node holding 2), forming a cycle. Running has_cycle makes fast lap the loop faster than slow; after three iterations the two pointers land on the same node, so the function returns True. find_cycle_start reruns the same race to find that meeting point, then resets one pointer to the head and advances both pointers one step at a time; this guarantees they meet exactly at the first node of the cycle, the node holding 2. The second list, [1, 2, 3], has no cycle at all, so fast simply runs off the end and has_cycle correctly returns False.

Why does resetting one pointer to the head work? Let the distance from the head to the start of the cycle be a, the distance from the cycle’s start to the meeting point be b, and the remaining distance around the cycle back to the start be c. By the time the pointers meet, a turns out to equal c plus a whole number of extra laps around the cycle. So a pointer walking from the head, distance a, and a pointer walking from the meeting point, distance c before wrapping, arrive at the cycle’s start at the same time, moving one step at a time.

Example 3: The Happy Number Problem

This example applies the exact same slow and fast walk to a sequence of numbers instead of linked list nodes.

def get_next(number: int) -> int:
    total = 0
    while number > 0:
        digit = number % 10
        total += digit * digit
        number //= 10
    return total

def is_happy(n: int) -> bool:
    slow = n
    fast = get_next(n)
    while fast != 1 and slow != fast:
        slow = get_next(slow)
        fast = get_next(get_next(fast))
    return fast == 1

if __name__ == "__main__":
    for number in [19, 2, 7]:
        result = is_happy(number)
        print(f"{number} is happy: {result}")

Output:

19 is happy: True
2 is happy: False
7 is happy: True

A number is happy if repeatedly replacing it with the sum of the squares of its digits eventually reaches 1; if it is not happy, the process falls into an endless loop that never reaches 1. There is no linked list here, but the sequence of transformations behaves exactly like one: each number points to the next number produced by get_next. Running slow one step and fast two steps through this implicit sequence detects a cycle exactly the same way it would in a list. For 19, the sequence reaches 1 before the pointers ever meet, so it is happy. For 2, the sequence falls into the repeating cycle 4, 16, 37, 58, 89, 145, 42, 20, 4, ..., so slow and fast eventually land on the same value and the function returns False. 7 reaches 1 and is happy as well.

How It Works, Step by Step

Let’s trace find_middle on the list [1, 2, 3, 4, 5, 6, 7] node by node. Both pointers start at the node holding 1.

Iteration	Condition checked	slow moves to	fast moves to
start	—	1	1
1	fast=1, fast.next=2, continue	2	3
2	fast=3, fast.next=4, continue	3	5
3	fast=5, fast.next=6, continue	4	7
4	fast=7, fast.next=None, stop	4 (unchanged)	7 (unchanged)

The loop condition while fast is not None and fast.next is not None is checked before each step. On the fourth check, fast is the node holding 7, and its next is None, so the loop body never runs a fourth time, and slow is left sitting on 4, the true middle of the seven-node list.

Common Mistakes

Mistake 1: Checking fast.next.next Before Confirming fast.next Exists

The loop condition must guard both hops fast is about to take. A common bug is writing the loop as if only the first hop needs checking:

def has_cycle_buggy(head: "ListNode | None") -> bool:
    slow = head
    fast = head
    while fast.next.next is not None:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            return True
    return False

This raises AttributeError: 'NoneType' object has no attribute 'next' as soon as fast.next is None, because Python still evaluates fast.next.next and there is no .next to read on None. It also never checks whether fast itself is None. The fix is to check both pointers, left to right, so Python’s short-circuit evaluation stops before touching a missing attribute:

def has_cycle_fixed(head: "ListNode | None") -> bool:
    slow = head
    fast = head
    while fast is not None and fast.next is not None:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            return True
    return False

Because and short-circuits, Python only evaluates fast.next once it already knows fast is not None, and the loop body only runs when there is room to safely take both steps.

Mistake 2: Comparing Node Values Instead of Node Identity

To detect that slow and fast have met, you must compare whether they are the same node, not whether they hold the same value. Using == on values is a subtle bug that only shows up on lists with duplicate values:

def has_cycle_buggy(head: "ListNode | None") -> bool:
    slow = head
    fast = head
    while fast is not None and fast.next is not None:
        slow = slow.next
        fast = fast.next.next
        if slow.val == fast.val:
            return True
    return False

If the list is 1 -> 2 -> 1 -> 2 -> 1 -> 2 with no cycle at all, slow and fast can land on two different nodes that both happen to hold 1, producing a false positive. The fix is to compare node identity with is, which checks that slow and fast refer to the exact same object in memory:

def has_cycle_fixed(head: "ListNode | None") -> bool:
    slow = head
    fast = head
    while fast is not None and fast.next is not None:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            return True
    return False

Best Practices

• Always guard both hops of the fast pointer with while fast is not None and fast.next is not None, in that order, so Python’s short-circuiting never dereferences None.
• Compare pointer identity with is, not ==, when checking whether slow and fast have met; you are asking whether these are the same node, not whether they hold equal values.
• Reach for fast and slow pointers whenever you would otherwise reach for a set to track have-I-seen-this-before in a sequence with a bounded number of distinct states; it turns O(n) space into O(1).
• For find-the-middle problems, remember that with an even number of nodes this loop stops with slow on the second of the two middle nodes; start fast at head.next instead of head if you need the first middle node instead.
• Do not use fast and slow pointers just to iterate a list once. If you do not need cycle detection, a midpoint, or a meeting point, a plain single-pointer loop is simpler and clearer.
• When the sequence is not really a linked list, such as numbers or array indices, write a small get-next-style function that computes the next state, then reuse the exact same slow and fast loop; the technique does not care what the states represent.

Practice Exercises

1. Palindrome Linked List: Given the head of a singly linked list, determine whether it reads the same forwards and backwards. Use fast and slow pointers to find the middle, reverse the second half, and compare it to the first half. For 1 -> 2 -> 2 -> 1 your function should return True; for 1 -> 2 -> 3 it should return False.
2. Find the Duplicate Number: Given an array of n + 1 integers where every value is between 1 and n inclusive and exactly one value is repeated, find the duplicate using O(1) extra space. Hint: treat the array as an implicit linked list where index i points to index arr[i], and reuse Floyd’s cycle detection.
3. First Middle Node: Starting from the find_middle function in Example 1, adjust it so that for an even-length list like 1 -> 2 -> 3 -> 4 it returns the first of the two middle nodes, value 2, instead of the second. Hint: change where fast starts.

Summary

• Fast and slow pointers move through a sequence at different speeds, typically one step versus two, to find a midpoint or detect a cycle without extra memory.
• With no cycle, fast reaches the end first; with a cycle, fast is guaranteed to eventually meet slow because the gap between them shrinks by exactly one node every iteration.
• Finding a midpoint and detecting a cycle both run in O(n) time and O(1) space, the same time complexity as a hash-set approach but without the extra O(n) space.
• Floyd’s algorithm extends cycle detection to also locate the exact starting node of the cycle, using a second phase that walks two single-speed pointers from the head and the meeting point.
• The technique generalizes beyond linked lists to any apply-a-function-repeatedly sequence, such as the happy number problem.
• Always check fast is not None and fast.next is not None in that order, and always compare meeting points with is, never ==.