Fast and slow pointers

Imagine you’re following a trail of clues in a scavenger hunt. If the trail loops back on itself, you’d walk forever. But if you send two people — one walking, one jogging — the jogger will eventually lap the walker inside the loop. That’s Floyd’s algorithm in one sentence.

That picture is the whole idea behind fast and slow pointers. You keep two references into a linked structure:

• slow moves 1 step at a time
• fast moves 2 steps at a time

If there is no cycle, fast runs out of nodes and hits null first. If there is a cycle, fast eventually catches slow inside the loop.

This is one of those rare patterns that feels almost magical the first time you see it, then shows up everywhere: linked list cycle detection, finding the middle node, locating the entry point of a loop, checking whether a linked list is a palindrome, and even solving array problems like Find the Duplicate Number.

The core idea in plain English

A linked list only lets you move forward. That means you cannot jump backward, mark visited nodes in place, or ask the list how long it is unless you walk it.

Fast/slow pointers turn that limitation into a strength.

Think of a circular running track:

• the walker gains 1 step per round of movement
• the jogger gains 2 steps per round
• so the jogger gains 1 extra step on the walker every time

Once both are on the circular part, the jogger closes the gap steadily. If the loop has length C, the gap can only be 0, 1, 2, ..., C-1. Since the gap shrinks by 1 (modulo C) every iteration, they must meet within at most C moves.

That gives us the big result:

• Time: O(n)
• Extra space: O(1)

No hash set. No marking nodes. No modifying the structure.

The math behind why fast catches slow

Let’s make the proof concrete.

Suppose the cycle length is C = 4. Once both pointers are inside the cycle, imagine the gap between them is 3 nodes.

After one iteration:

• slow moves 1
• fast moves 2
• so fast gains exactly 1 node on slow

That changes the gap from 3 to 2. Then 2 to 1. Then 1 to 0. At gap 0, they are on the same node.

The same reasoning works for any cycle length:

1. After both pointers enter the loop, they keep moving forever.
2. fast gains 1 node per iteration relative to slow.
3. The distance between them is measured modulo the cycle length C.
4. Repeatedly adding 1 modulo C must eventually land on 0.

So fast always catches slow in at most C iterations after both are inside the cycle.

That is why Floyd’s algorithm is so elegant: it uses a tiny amount of state, but the math guarantees success.

Application 1: Detecting a cycle in a linked list

This is the classic use case.

If fast reaches null, the list ends, so there is no cycle. If slow == fast at any point after moving, the list must contain a cycle.

For the visualization above, the structure is:

1 → 2 → 3 → 4 → 5 → 6 → 3

So node 6 points back to node 3.

Let’s step through it:

• slow = 1, fast = 1
• slow = 2, fast = 3
• slow = 3, fast = 5
• slow = 4, fast = 3
• slow = 5, fast = 5 → meet

Why is that enough to prove a cycle exists? Because in a normal acyclic list, fast can never come back around. It only moves forward. The only way it can land on the same node as slow again is if the structure loops.

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


def has_cycle(head: ListNode | None) -> bool:
    slow = head
    fast = head

    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next

        if slow == fast:
            return True

    return False

class ListNode {
    int val;
    ListNode next;

    ListNode(int val) {
        this.val = val;
    }
}

public static boolean hasCycle(ListNode head) {
    ListNode slow = head;
    ListNode fast = head;

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

        if (slow == fast) {
            return true;
        }
    }

    return false;
}

struct ListNode {
    int val;
    ListNode* next;

    ListNode(int x) : val(x), next(nullptr) {}
};

bool hasCycle(ListNode* head) {
    ListNode* slow = head;
    ListNode* fast = head;

    while (fast != nullptr && fast->next != nullptr) {
        slow = slow->next;
        fast = fast->next->next;

        if (slow == fast) {
            return true;
        }
    }

    return false;
}

Complexity: O(n) time, O(1) space.

Application 2: Finding the middle of a linked list

The same pattern works even when there is no cycle.

If fast moves twice as quickly as slow, then when fast has walked the whole list, slow has walked only half of it.

That means slow ends at the middle.

Step through 10 → 20 → 30 → 40 → 50:

• start: slow = 10, fast = 10
• move once: slow = 20, fast = 30
• move again: slow = 30, fast = 50
• fast is at the end, so slow is at the middle

This is useful because linked lists do not support random indexing. You cannot jump directly to n / 2. Fast/slow pointers find the middle in one pass.

That one-pass middle finder is the standard split step in merge sort on linked lists.

def middle_node(head: ListNode | None) -> ListNode | None:
    slow = head
    fast = head

    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next

    return slow

public static ListNode middleNode(ListNode head) {
    ListNode slow = head;
    ListNode fast = head;

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

    return slow;
}

ListNode* middleNode(ListNode* head) {
    ListNode* slow = head;
    ListNode* fast = head;

    while (fast != nullptr && fast->next != nullptr) {
        slow = slow->next;
        fast = fast->next->next;
    }

    return slow;
}

A small detail: on an even-length list, this version returns the second middle. For 1 → 2 → 3 → 4, it returns 3. That is usually what interview problems expect, but always check the problem statement.

Application 3: Finding the start of the cycle

Cycle detection tells you whether a loop exists. Floyd’s second phase tells you where the loop begins.

After slow and fast meet:

1. Reset one pointer to head
2. Leave the other at the meeting point
3. Move both one step at a time
4. The node where they meet is the cycle start

That last step feels like a trick, so let’s prove it with simple algebra.

Let:

• a = distance from head to the cycle start
• b = distance from cycle start to the meeting point
• C = cycle length

When they meet the first time:

• slow has traveled a + b
• fast has traveled a + b + kC for some integer k because it has done extra full laps

Since fast moves twice as fast:

a + b + kC = 2(a + b)

So:

kC = a + b

Rearrange:

a = kC - b = (k - 1)C + (C - b)

That equation says something very concrete.

If you start from the meeting point, you need C - b more steps to finish the current lap and reach the cycle start again. Adding (k - 1)C just means extra full loops, which land on the same node.

So:

• walking a steps from head
• and walking a steps from the meeting point

bring both pointers to the cycle start.

That is why phase 2 works. Step through both phases on a list where node 2 is the cycle start:

def detect_cycle_start(head: ListNode | None) -> ListNode | None:
    slow = head
    fast = head

    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next

        if slow == fast:
            finder = head
            while finder != slow:
                finder = finder.next
                slow = slow.next
            return finder

    return None

public static ListNode detectCycleStart(ListNode head) {
    ListNode slow = head;
    ListNode fast = head;

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

        if (slow == fast) {
            ListNode finder = head;
            while (finder != slow) {
                finder = finder.next;
                slow = slow.next;
            }
            return finder;
        }
    }

    return null;
}

ListNode* detectCycleStart(ListNode* head) {
    ListNode* slow = head;
    ListNode* fast = head;

    while (fast != nullptr && fast->next != nullptr) {
        slow = slow->next;
        fast = fast->next->next;

        if (slow == fast) {
            ListNode* finder = head;
            while (finder != slow) {
                finder = finder->next;
                slow = slow->next;
            }
            return finder;
        }
    }

    return nullptr;
}

A concrete example helps. Suppose:

• a = 2 nodes before the cycle
• b = 3 nodes from cycle start to meeting point
• C = 5

Then a + b = 5, which is exactly one full cycle. Reset one pointer to the head and move both one step at a time:

• head pointer needs 2 steps to reach the cycle start
• meeting pointer also needs 2 steps to wrap around from b = 3 to the cycle entry

They meet at the cycle start.

Application 4: Checking whether a linked list is a palindrome

Fast/slow pointers are often part of a larger recipe, not the whole solution.

A palindrome linked list check is a perfect example.

Steps:

1. Use fast/slow to find the middle
2. Reverse the second half of the list
3. Compare the first half with the reversed second half
4. Optionally restore the list to its original order

Step 1 is exactly the fast/slow pattern — watch it find the middle of 1 → 2 → 3 → 2 → 1:

For 1 → 2 → 3 → 2 → 1:

• middle is 3
• reverse the second half 2 → 1 into 1 → 2
• compare left half 1 → 2 with right half 1 → 2
• all pairs match, so the list is a palindrome

The important lesson is architectural: fast/slow finds the split point, and a second technique — reversal — finishes the job. Many good linked-list solutions are combinations like that.

If the list has even length, like 1 → 2 → 2 → 1, the same approach still works. You find the middle boundary, reverse the second half, and compare corresponding nodes.

Application 5: Floyd’s algorithm on arrays to find a duplicate

This is the surprising one.

Problem: you have an array of n + 1 integers where every value is in the range [1, n]. Exactly one value is duplicated. Find it using O(1) extra space.

This is LeetCode #287.

At first glance, it doesn’t look like a linked-list problem at all. But you can reinterpret the array as a functional graph:

• each index is a node
• arr[i] is the next pointer

For example, with:

arr = [1, 3, 4, 2, 2]

Think of the jumps like this:

• 0 → 1
• 1 → 3
• 3 → 2
• 2 → 4
• 4 → 2

Now you can see the loop: 2 ↔ 4.

Why does a duplicate create a cycle? Because two different indices point into the same next node. That creates a merge, and in this constrained graph, a merge forces a loop.

So the algorithm is identical in spirit:

• slow = arr[slow]
• fast = arr[arr[fast]]
• find a meeting point
• reset one pointer
• move both at speed 1
• the meeting node is the duplicate value

Watch Floyd’s algorithm find the duplicate 2 in [1, 3, 4, 2, 2]:

def find_duplicate(nums: list[int]) -> int:
    slow = nums[0]
    fast = nums[0]

    while True:
        slow = nums[slow]
        fast = nums[nums[fast]]
        if slow == fast:
            break

    finder = nums[0]
    while finder != slow:
        finder = nums[finder]
        slow = nums[slow]

    return finder

public static int findDuplicate(int[] nums) {
    int slow = nums[0];
    int fast = nums[0];

    do {
        slow = nums[slow];
        fast = nums[nums[fast]];
    } while (slow != fast);

    int finder = nums[0];
    while (finder != slow) {
        finder = nums[finder];
        slow = nums[slow];
    }

    return finder;
}

int findDuplicate(vector<int>& nums) {
    int slow = nums[0];
    int fast = nums[0];

    do {
        slow = nums[slow];
        fast = nums[nums[fast]];
    } while (slow != fast);

    int finder = nums[0];
    while (finder != slow) {
        finder = nums[finder];
        slow = nums[slow];
    }

    return finder;
}

This section is worth pausing on because it expands the pattern beyond linked lists.

Floyd’s algorithm works on any structure where each state has exactly one “next” state.

That kind of structure is called a functional graph.

Summary table

Common pitfalls

These bugs show up constantly:

• Forgetting fast.next before reading fast.next.next. In Java or C++, that becomes a null-pointer crash. In Python, it becomes an attribute error.
• Not handling lists with 0 or 1 nodes. An empty list and a single-node list are both valid inputs.
• Forgetting to reset a pointer in phase 2. If you do not move one pointer back to head, you will not find the cycle start.
• Assuming this only works on linked lists. It works on any functional graph: linked lists, arrays-as-next-pointers, and even repeated numeric transformations.
• Mixing up “first middle” and “second middle.” On even-length lists, the exact loop condition determines which middle you get.

A good debugging habit is to manually trace a tiny example like 1 → 2 → 3 → 4 → 5 or 1 → 2 → 3 → 4 → 5 → 3 and write down (slow, fast) after each iteration.

Practice problems

• Linked List Cycle (#141) - Easy
• Linked List Cycle II (#142) - Medium
• Middle of the Linked List (#876) - Easy
• Find the Duplicate Number (#287) - Medium
• Palindrome Linked List (#234) - Easy
• Happy Number (#202) - Easy

Happy Number is a fun stretch problem because the “next pointer” is not stored in a list at all. The next state is “replace the number with the sum of the squares of its digits.” If the sequence falls into a loop that never reaches 1, Floyd’s cycle detection finds it.

Key takeaways

1. Fast/slow pointers trade extra speed for insight: the relative speed difference reveals structure.
2. If a linked list has a cycle, fast must eventually catch slow.
3. If there is no cycle, fast reaches null first.
4. The same pattern finds the middle node in one pass.
5. Floyd’s second phase locates the cycle entry with a clean algebraic guarantee.
6. The idea extends beyond linked lists to functional graphs, including array duplicate problems.

What’s next

This post was your bridge from array-style scanning to pointer-chasing structures. Next comes post 13: singly linked lists, which starts Part 4: Linear Structures and makes these pointer tricks feel much more natural in the bigger linked-list toolbox.