Middle of a Linked List

The Dumb Approach

1. Convert into an array: Traverse through the Linked List → Add nodes into an array.
2. Find middle element of the array: Roughly, arr[len / 2].
3. Say "mehh!" and go home. Who cares.

The Slow / Fast Pointer Approach

The whole idea is one pointer moves 2 nodes at a time while the other moves just one, so that when the faster pointer reaches the end of the list, the slower pointer has reached the middle.

slow = slow.next;
fast = fast.next.next;

Now the exit statement depends on whether the length of the list is even or odd.

Imagine, you start at the first node (0th-index) and your list has exactly 11 nodes (odd). That makes the 6th node (5th-index) the middle node. To reach the end of the list, the fast pointer traversal looks like:

0 -> 2 -> 4 -> 6 -> 8 -> 10

That’s 5 moves. And that’s exactly the index where you find the middle node. So the exit condition becomes:

fast.next === null // reached last node

Now in the case of an even number, let’s take 10. We have 2 middles here: the 5th and the 6th node. The fast pointer traversal looks like:

0 -> 2 -> 4 -> 6 -> 8 -> null

Depending on your problem requirements (whether it expects the first or second middle node), your exit conditions are:

1. 2nd of the 2 (LeetCode standard): fast === null
2. 1st of the 2: fast.next.next === null

The Final Code

function middleNode(head: ListNode | null): ListNode | null {
  let slow = head;
  let fast = head;

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

  return slow;
}