Fast & Slow Pointers

Find Middle Node

When fast reaches the last node (or null), slow is at the exact middle. For even-length lists, this gives you the second middle node. Useful as a preprocessing step for merge sort on linked lists.

O(n)

O(1)

How It Works

Finding a linked list's middle without knowing its length normally takes two passes: count n, then walk n/2 nodes. Fast and slow pointers do it in one: slow steps once and fast steps twice per iteration, so when fast exhausts the list, slow has covered exactly half of it. With the loop condition fast != null && fast.next != null, an odd-length list leaves slow on the true middle and an even-length list leaves it on the second of the two middles.

Both versions are O(n) time and O(1) space, but the one-pass form matters for streams and is the standard preprocessing step for splitting a list — merge sort on lists and palindrome checking both start here.

Step-by-Step Visualization

Find middle of 1→2→3→4→5

S,F

Slow1

Fast1

1/4

Code

Java

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

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

  return slow; // Middle node
}

// 1→2→3→4→5 → returns node 3
// 1→2→3→4 → returns node 3 (second middle)

Tips & Gotchas

1When fast reaches the end, slow is at the middle

2For even-length lists, slow points to the second middle node

3Useful as a building block for merge sort on linked lists

Practice Problems

1Middle of the Linked List
2Palindrome Linked List
3Sort List
4Reorder List

About the Fast & Slow Pointers Pattern

Two pointers traverse the list at different speeds. The fast pointer moves 2 nodes per step, the slow pointer moves 1. This simple idea solves cycle detection (they'll meet inside the cycle) and midpoint finding (when fast reaches end, slow is at middle).

Key insight

Most linked list problems are about pointer manipulation. Draw it out! Fast & slow pointers detect cycles and find midpoints. In-place reversal is the other core technique.

Common Linked List Interview Problems

Reverse Linked List
Merge Two Sorted Lists
Linked List Cycle
Remove Nth Node From End
LRU Cache
Reorder List

Frequently Asked Questions

How do I get the first middle instead of the second for even lengths?

Start fast at head.next instead of head, or change the loop to check fast.next and fast.next.next. This offset matters when splitting: taking the first middle as the end of the left half yields balanced halves you can cleanly disconnect for merge sort.

Why prefer one pass over counting the length first?

Asymptotically they match at O(n), so the gain is practical: one traversal touches each node once, works when length is unknown upfront, and composes naturally into algorithms that immediately do something at the midpoint, like reversing the second half for a palindrome check.