3.6 Fast and Slow Pointers

Fast and slow pointers are two references that traverse the same linked structure at different speeds. Usually, the slow pointer moves one step at a time, while the fast pointer moves two steps at a time. This simple difference creates information about the shape of the list: whether a cycle exists, where the middle lies, or how to split the list into two parts.

Problem

You need to locate structural positions in a singly linked list without knowing its length in advance and without using extra memory.

Common targets include:

middle node
cycle meeting point
start of second half
k-th position from a relative boundary

A full preliminary pass can compute the length, but fast and slow pointers often avoid that extra traversal.

Basic Pattern

The standard loop is:

slow = head
fast = head

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

When the loop stops, slow is near the middle of the list.

For an odd-length list, slow points to the exact middle. For an even-length list, this version points to the second of the two middle nodes.

Finding the Middle

For the list:

a -> b -> c -> d -> e -> null

the algorithm ends with:

slow = c

For the list:

a -> b -> c -> d -> null

the algorithm ends with:

slow = c

This convention is useful when splitting a list into a first half and a second half that begins at slow.

First Middle vs Second Middle

Sometimes an algorithm needs the first middle in an even-length list. Use a different initialization:

slow = head
fast = head.next

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

For:

a -> b -> c -> d -> null

this version ends with:

slow = b

This is useful when slow must become the tail of the first half.

Splitting a List

To split a list into two halves, find the first middle, then cut after it.

slow = head
fast = head.next

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

second = slow.next
slow.next = null

first = head

For:

a -> b -> c -> d -> null

the result is:

first:  a -> b -> null
second: c -> d -> null

For:

a -> b -> c -> d -> e -> null

the result is:

first:  a -> b -> c -> null
second: d -> e -> null

Palindrome Check

Fast and slow pointers are often used to find the middle before reversing the second half.

slow = head
fast = head

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

second = reverse(slow)
first = head

while second != null:
  if first.value != second.value:
    return false
  first = first.next
  second = second.next

return true

This uses O(n) time and O(1) extra space, aside from the temporary reversal. In production code, you may restore the reversed half before returning.

Nth Node from the End

A related two-pointer pattern keeps a fixed gap instead of different speeds.

lead = head
follow = head

for i in 1..n:
  lead = lead.next

while lead != null:
  lead = lead.next
  follow = follow.next

return follow

When lead reaches the end, follow points to the nth node from the end.

This is not technically fast and slow movement, since both pointers move at the same speed after the gap is created. It belongs in the same family because the position of one pointer defines the position of the other.

Removing the Nth Node from the End

A sentinel handles deletion cleanly.

dummy.next = head

lead = dummy
follow = dummy

for i in 1..n+1:
  lead = lead.next

while lead != null:
  lead = lead.next
  follow = follow.next

follow.next = follow.next.next

return dummy.next

The gap is n + 1, so follow stops at the predecessor of the node to delete.

Complexity

Common Failure Modes

The most common bug is an unsafe loop guard. Since fast moves by two steps, the loop must verify both fast and fast.next before reading fast.next.next.

Another common bug is choosing the wrong middle convention. In even-length lists, decide whether the algorithm needs the first middle or the second middle before writing the loop.

A third bug is losing the second half while splitting. Save slow.next before assigning slow.next = null.

Key Insight

Fast and slow pointer algorithms extract global structure from local movement. They avoid storing length or visited nodes by maintaining a precise relationship between two references. The method works when the desired position can be described by a distance relation: half the list, one lap inside a cycle, or a fixed offset from the end.