Middle of a linked list

Easy TimeO(n) SpaceO(1)

A linked list cannot be indexed, so its middle is not simply available, and its length is not known in advance. Given the head of one, return the value at its middle node — for [1, 2, 3, 4, 5] that is 3. With an even number of nodes there are two middles, and the second of them is wanted. One pass through the list has to be enough.

Examples

Example 1

Input
head = buildList([1, 2, 3, 4, 5])
Output
3
Five nodes, and the third is the middle — its value is 3.

Example 2

Input
head = buildList([1, 2, 3, 4])
Output
3
Four nodes have two middles, 2 and 3, and the second is the one wanted.

The Code

function buildList(values) {
  let head = null;
  for (let i = values.length - 1; i >= 0; i--) {
    head = { val: values[i], next: head };
  }
  return head;
}
function middleNode(head) {
  let slow = head;
  let fast = head;
  while (fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;
  }
  return slow.val;
}
middleNode(buildList([1, 2, 3, 4, 5]));
Done

The first 9 calls, of 11. This one does not fit on a page.

Step through middleNode(buildList([1, 2, 3, 4, 5])) call by call

More like this

All linked lists examples (9) →