# 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:

```text id="zi82dj"
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:

```text id="chafh5"
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:

```text id="rts3l5"
a -> b -> c -> d -> e -> null
```

the algorithm ends with:

```text id="f4vwmj"
slow = c
```

For the list:

```text id="c9hd73"
a -> b -> c -> d -> null
```

the algorithm ends with:

```text id="5p9sr4"
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:

```text id="vd0ul1"
slow = head
fast = head.next

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

For:

```text id="jsewhs"
a -> b -> c -> d -> null
```

this version ends with:

```text id="ssrjut"
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.

```text id="f7kwmh"
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:

```text id="3yfw12"
a -> b -> c -> d -> null
```

the result is:

```text id="a1xbus"
first:  a -> b -> null
second: c -> d -> null
```

For:

```text id="dvzs06"
a -> b -> c -> d -> e -> null
```

the result is:

```text id="wpseve"
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.

```text id="c63ypl"
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.

```text id="l5pgy5"
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.

```text id="77p7fg"
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

| Operation           | Time | Space |
| ------------------- | ---: | ----: |
| Find middle         | O(n) |  O(1) |
| Split list          | O(n) |  O(1) |
| Find nth from end   | O(n) |  O(1) |
| Remove nth from end | O(n) |  O(1) |
| Detect cycle        | O(n) |  O(1) |

## 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.