Edit Problem

Title

Problem URL

Difficulty

Tags

Fast & Slow Pointers

Go file path (optional)

Notes (optional)

## What It Does

This function returns the middle node of a singly linked list using the same tortoise-and-hare pointer trick as cycle detection — but here the goal is position, not collision. `slow` moves one step at a time while `fast` moves two, so by the time `fast` exhausts the list, `slow` is sitting exactly at the midpoint.

For odd-length lists it's exact: `1 → 2 → 3 → 4 → 5` returns the node with value `3`. For even-length lists it returns the **second** middle: `1 → 2 → 3 → 4` returns `3`, not `2` — a consequence of `fast` running out one step past center.

---

## Complexity Analysis

**Time Complexity: O(n)**
`fast` traverses the list in ~n/2 iterations, so the loop runs exactly half as many times as there are nodes — still linear.

**Space Complexity: O(1)**
Just two pointers. No allocations, no recursion.

---

## A Few Notes

**This is almost identical to the cycle detection solution.** Same loop guard (`fast != nil && fast.Next != nil`), same pointer movement — the only difference is what you *do* with the result. There's no collision check; you just return `slow` when the loop exits.

**The even-length bias is a deliberate consequence, not a bug.** If you wanted the *first* middle instead (`2` instead of `3` for a 4-node list), you'd initialize `fast = head.Next` before the loop. Which middle you want depends on the problem — many downstream uses (like palindrome checking after splitting) specifically need the second middle.

**This is a common sub-step, not usually a standalone problem.** You'll see `findMiddle` called inside solutions for reversing the second half of a list, checking palindromes, or merge sort on linked lists — it's a building block more than an end goal.

First solved

May 20, 2026