Find Middle of Linked List

Before we start

This is the simplest fast/slow pointer application. It deserves its own chapter because it is the building block for three harder patterns: palindrome linked list, merge sort on a linked list, and the reorder-list problem (Chapter 4.7). Once you understand exactly which node slow lands on — and why there are two valid "middles" for even-length lists — you will never get the off-by-one wrong again.

Picture this first (no code yet)

The actual problem

Middle of the Linked List (LC #876):

Given the head of a linked list, return the middle node. If there are two middle nodes (even length), return the second middle node.

1 → 2 → 3 → 4 → 5   →  return node 3   (length 5, one middle)
1 → 2 → 3 → 4        →  return node 3   (length 4, second of two middles)

Without fast/slow: traverse once to count length (say n), traverse again to position n//2. Two passes, O(n) time, O(1) space.

With fast/slow: one pass, O(n) time, O(1) space.

The turning point

Start: slow=1, fast=1
Step 1: slow=2, fast=3
Step 2: slow=3, fast=5
Next: fast.next is None → stop.
Slow is at node 3 ✅ (middle of 5)

Start: slow=1, fast=1
Step 1: slow=2, fast=3
Step 2: slow=3, fast=None (fast=3.next.next=4.next=None)

Wait — let me re-check. fast=3, fast.next=4, fast.next.next=None.
While condition: fast and fast.next → fast=3 (truthy), fast.next=4 (truthy) → enter loop.
slow=3, fast=None.
Now while: fast=None → exit.
Slow is at node 3 ✅ (second of two middles for length 4)

The one idea to remember

The code, line by line

def middleNode(head):
    slow = fast = head

    while fast and fast.next:       # fast needs 2 steps each iteration
        slow = slow.next
        fast = fast.next.next

    return slow                     # slow is at middle

Three lines of logic. Read against the story:

• while fast and fast.next: — continue while fast can take a full two-step. fast checks the current node is not None (so fast.next is safe to access). fast.next checks the next node is not None (so fast.next.next is safe to access).
• fast = fast.next.next — two steps in one assignment.
• return slow — slow has moved exactly half the steps fast moved.

Watch it happen, frame by frame

Odd length: 1 → 2 → 3 → 4 → 5

     slow  fast
  ①  [1]   [1]
  ②  [2]   [3]     (after step 1)
  ③  [3]   [5]     (after step 2)

fast.next = None → while exits.
Return slow = node 3  ✅

Even length: 1 → 2 → 3 → 4

     slow  fast
  ①  [1]   [1]
  ②  [2]   [3]     (after step 1)
  ③  [3]   none    (fast=3.next.next=None)

fast = None → while exits.
Return slow = node 3  ✅  (second middle)

Length 2: 1 → 2

slow=1, fast=1
While: fast=1 (ok), fast.next=2 (ok) → enter.
slow=2, fast=None.
While: fast=None → exit.
Return slow = node 2  ✅  (second middle of length-2 list)

Length 1: 1

slow=1, fast=1
While: fast=1 (ok), fast.next=None → exit immediately.
Return slow = node 1  ✅

The first vs second middle question

Some problems want the first middle (for even-length lists). The standard code above gives the second middle (LC #876 asks for second). To get the first middle, move fast one step ahead at the start:

# Returns FIRST middle for even-length (second for odd — same result)
slow, fast = head, head.next     # fast starts one ahead
while fast and fast.next:
    slow = slow.next
    fast = fast.next.next
return slow

Which to use? Read the problem. For Palindrome Linked List (Chapter 4.7), you need the first middle so you can reverse the second half cleanly. For LC #876, you return the second middle. Know both and choose deliberately.

Application: Palindrome Linked List (LC #234)

The full algorithm:

1. Find the middle (first middle for even-length).
2. Reverse the second half (Chapter 4.3).
3. Compare node-by-node with the first half.
4. (Optional) Restore the list.

def isPalindrome(head):
    # Step 1: find first middle
    slow, fast = head, head.next
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next

    # Step 2: reverse second half
    prev, curr = None, slow.next
    while curr:
        nxt  = curr.next
        curr.next = prev
        prev = curr
        curr = nxt
    # prev is now the head of the reversed second half

    # Step 3: compare
    left, right = head, prev
    while right:               # right half may be shorter for odd length
        if left.val != right.val:
            return False
        left  = left.next
        right = right.next
    return True

This whole algorithm is O(n) time, O(1) space — no extra array.

Where to spot this pattern

Trigger words:

• "find the middle of a linked list"
• "split the list in half" (merge sort on lists)
• "palindrome linked list" — always starts with finding the middle
• "reorder list" — split, reverse second half, merge (Chapter 4.7)

Common traps

slow = fast = head
while fast and fast.next:
    slow = slow.next
    fast = fast.next.next
# slow is at SECOND middle (or only middle for odd length)

Check yourself

Start: slow=1, fast=1
Step 1: slow=2, fast=3
Step 2: slow=3, fast=5
Step 3: slow=4, fast=None (fast=5.next.next=None)
Return node 4 — the SECOND middle (positions 3 and 4 are the two middles; second = node 4)

Start: slow=1, fast=2
Step 1: slow=2, fast=4
Step 2: slow=3, fast=None (fast=4.next.next=None)
Return node 3 — the FIRST middle

Practice problems

Next up: Reverse a Linked List — the most fundamental linked list operation: three pointers, one pass, O(1) space, and the basis for every "reverse a portion" problem.