Introduction to Fast & Slow Pointers Pattern

Why must the pointers meet inside a cycle?

After both pointers enter the cycle, fast gains one node on slow during every step. The distance between them becomes smaller around the loop. Eventually, that distance becomes zero.

Each pointer moves through at most a linear number of nodes. Therefore, the time complexity is O(N).

The algorithm stores only two pointers. Its extra space complexity is O(1).

Recognize it when

Fast and Slow Pointers may be useful when:

• The input is a linked list.
• The problem asks whether a cycle exists.
• The problem asks for the middle of a linked list.
• The input is a sequence where each value creates the next value.
• Your first solution stores every visited node in a hash set.
• The problem asks for constant extra space.

The Happy Number problem is an example of a generated sequence. Each number produces the next number. A repeating number creates a cycle.

Do not use this pattern when:

• You need a pair or triplet in a sorted array. Use Two Pointers.
• You need a contiguous part of an array or string. Use Sliding Window.
• You must reverse the links in a linked list. Use In-place Reversal of a Linked List.
• You only need the previous node while walking forward. One previous pointer is simpler.

The template

function hasCycle(head):
    slow = head
    fast = head

    while fast is not empty and fast.next is not empty:
        slow = slow.next
        fast = fast.next.next

        if slow == fast:
            return true

    return false

Two details are important.

First, check fast before checking fast.next. If fast is empty, reading fast.next causes an error.

Second, compare the nodes themselves. Do not compare only their values. Two different nodes can contain the same value.

To find the middle of a list, use the same loop without the meeting test. When fast reaches the end, slow is near the middle.

Variants in this chapter

Learn cycle detection first. The other variants reuse the same pointer movement.

Watch out for

• Checking fast.next before fast. Always confirm that fast exists first.
• Comparing node values. Compare node identity because different nodes may store equal values.
• Moving fast without checking both steps. The loop must check both fast and fast.next.
• Assuming the first meeting point starts the cycle. Finding the start requires a second phase.
• Ignoring even-length lists. Two middle nodes exist, so check which one the problem expects.
• Changing the structure by mistake. These pointers move through the list; they do not change any next reference.

How this compares with nearby patterns

Both this pattern and Two Pointers use two positions. The rule for moving them is different.

In Two Pointers, values usually decide which pointer moves. In Fast and Slow Pointers, the two speeds are decided before the loop starts.

Key takeaways

• slow usually moves one step, and fast usually moves two steps.
• If a cycle exists, the two pointers eventually meet.
• If fast reaches the end, no cycle exists.
• Check fast before fast.next.
• Compare nodes, not only the values inside them.
• The pattern takes O(N) time and O(1) extra space.

Now apply this pattern to LinkedList Cycle.