Find Middle Node | Fast Slow Pointers | Linked List

Overview

Finding the middle node of a linked list means locating the node at (or near) the center in one pass and O(1) extra space. The standard approach is fast and slow pointers: slow moves one step, fast moves two steps; when fast reaches the end, slow is at the middle. For even-length lists you must decide whether to return the first or second of the two middle nodes.

Why it works: Fast covers twice the distance of slow, so when fast has reached the end (after n steps for slow), slow has moved n/2 steps and is at the middle.

When to Use

Get the middle node — e.g. for display, for splitting, or as part of another algorithm.
Palindrome linked list — find middle, reverse second half, compare.
Reorder list — find middle, reverse second half, merge alternately.
Merge sort on list — find middle to split the list into two halves.

How It Works

Start slow = head, fast = head.
Loop: while fast and fast.next are non-null, do slow = slow.next, fast = fast.next.next.
Second middle (even length): Stop when fast === null. Example: [1,2,3,4] → slow ends at 3.
First middle (even length): Stop when fast.next === null (i.e. do not move slow on the iteration when fast lands on the last node). Example: [1,2,3,4] → slow ends at 2.
Handle empty/single-node list: if head === null return null; for one node, slow stays at head.

Example 1: Return Second Middle (LeetCode-style)

Problem: Given the head of a singly linked list, return the middle node. If there are two middle nodes, return the second one (e.g. [1,2,3,4] → 3).

function middleNode(head: ListNode | null): ListNode | null {
  if (head === null) return null;
  let slow: ListNode | null = head;
  let fast: ListNode | null = head;
  while (fast !== null && fast.next !== null) {
    slow = slow!.next;
    fast = fast.next.next;
  }
  return slow;
}

Time: O(n), Space: O(1).

Example 2: Return First Middle (for Split / Merge Sort)

Problem: Return the first middle so the list can be split into two halves (e.g. [1,2,3,4] → 2; left = [1,2], right = [3,4]).

Stop when fast.next === null so that when fast is on the last node, we do not advance slow again:

function findFirstMiddle(head: ListNode | null): ListNode | null {
  if (head === null || head.next === null) return head;
  let slow: ListNode | null = head;
  let fast: ListNode | null = head;
  while (fast.next !== null && fast.next.next !== null) {
    slow = slow!.next;
    fast = fast.next.next;
  }
  return slow;
}

For [1,2,3,4], slow stays at 2; you can set mid = slow.next for the start of the right half and slow.next = null to split.

Example 3: Use Middle in Merge Sort (Split)

Problem: Split the list into two halves for recursive merge sort.

function splitMiddle(head: ListNode | null): [ListNode | null, ListNode | null] {
  if (head === null || head.next === null) return [head, null];
  let slow: ListNode | null = head;
  let fast: ListNode | null = head;
  while (fast.next !== null && fast.next.next !== null) {
    slow = slow!.next;
    fast = fast.next.next;
  }
  const right = slow!.next;
  slow!.next = null;
  return [head, right];
}

Example 4: Palindrome (Middle + Reverse Second Half)

Find the middle, reverse from the node after slow (or from slow for "second middle" style), then compare first half with reversed second half. See Palindrome Linked List and Fast and Slow Pointers.

Edge Cases

Empty list — Return null.
Single node — Return that node; loop may not run (fast.next is null).
Two nodes — Second middle: slow at second node. First middle: slow at first node.
Even vs odd — Choose first or second middle by loop condition as above.

Common Mistakes

Null checks — Ensure fast and fast.next are checked before advancing to avoid null dereference.
First vs second middle — Use fast.next === null (stop before last step) for first middle; fast === null (after moving) for second middle.
Splitting for merge sort — Set mid = slow.next, then slow.next = null so the list is actually split; don't forget to cut the link.

Time and Space Complexity

Time: O(n) — one pass.
Space: O(1) — two pointers.

Summary

Middle node: fast and slow pointers; when fast reaches the end, slow is at the middle. Choose first or second middle by when you stop.
Use in Palindrome Linked List, Reorder List, and Sort List (merge sort split).

See Fast and Slow Pointers for the general pattern.

Finding the Middle Node