Reorder List

Difficulty: Medium

You're given the head of a singly linked list with nodes, in order, holding values L0, L1, L2, ..., Ln. Rearrange the nodes in place (without just copying the values into a new structure) so the list instead reads L0, Ln, L1, Ln-1, L2, Ln-2, and so on — alternating one node from the front of the original order with one from the back, working inward.

You're changing the pointers between the existing nodes, not swapping the values stored inside them.

Examples

Input: head = [1, 2, 3, 4]
Output: [1, 4, 2, 3]

Input: head = [1, 2, 3, 4, 5]
Output: [1, 5, 2, 4, 3]

Input: head = [1]
Output: [1]

A single node has nothing to interleave with.

Constraints

The number of nodes is between 1 and 5 * 10^4.
1 <= Node.val <= 1000

Approach

A direct approach: drop every node reference into an array (this gives you random access), then use two indices, one starting at the front and one at the back, stitching the list back together by alternating between them.

The more memory-efficient approach avoids the array entirely. First, find the middle of the list using a fast/slow pointer. Then reverse the second half in place, so its nodes now come out in exactly the back-to-front order you need. Finally, zipper the first half and the reversed second half together one node at a time, which produces the required order without ever needing random access.

Solutions

Brute Force — Random Access via Array

Collect every node reference into an array, in order. Then use two indices — one starting at the front, one at the back — and rewire each node's next pointer to alternate between them, moving the indices toward each other until they meet.

class ListNode {
  constructor(val, next = null) {
    this.val = val;
    this.next = next;
  }
}

function reorderList(head) {
  if (!head) return;

  const nodes = [];
  let curr = head;
  while (curr) {
    nodes.push(curr);
    curr = curr.next;
  }

  let i = 0;
  let j = nodes.length - 1;

  while (i < j) {
    nodes[i].next = nodes[j];
    i++;
    if (i === j) break;
    nodes[j].next = nodes[i];
    j--;
  }

  nodes[i].next = null; // whichever node ends up last must terminate the list
}

Time: O(n) · Space: O(n)

Optimal — Split, Reverse Second Half, Merge

First, locate the middle of the list with a slow pointer (one step at a time) and a fast pointer (two steps at a time) — when the fast pointer runs out of room, the slow pointer sits at the middle. Cut the list there into two halves.

Reverse the second half in place, so walking it front to back now yields the original list's values back to front.

Finally, weave the first half and the reversed second half together: take one node from the first half, then one from the reversed second half, and repeat, re-pointing next as you go.

class ListNode {
  constructor(val, next = null) {
    this.val = val;
    this.next = next;
  }
}

function reorderList(head) {
  if (!head || !head.next) return;

  // 1. Find the middle.
  let slow = head;
  let fast = head;
  while (fast.next && fast.next.next) {
    slow = slow.next;
    fast = fast.next.next;
  }

  // 2. Split and reverse the second half.
  let second = slow.next;
  slow.next = null;
  let prev = null;
  while (second) {
    const next = second.next;
    second.next = prev;
    prev = second;
    second = next;
  }

  // 3. Merge the first half with the reversed second half.
  let first = head;
  second = prev;
  while (second) {
    const firstNext = first.next;
    const secondNext = second.next;
    first.next = second;
    second.next = firstNext;
    first = firstNext;
    second = secondNext;
  }
}

Time: O(n) · Space: O(1)