Marauder Bot

Problem

You are given the head of a singly linked list. Rearrange its nodes in place so that the first node is followed by the last node, then the second node, then the second-to-last node, and so on alternating from the front and back toward the middle, without swapping the values, only the links.

Example. The list 1 -> 2 -> 3 -> 4 becomes 1 -> 4 -> 2 -> 3.

Key idea

Reaching arbitrary positions from both ends of a singly linked list is awkward, since there is no way to walk backward. Copying every node into an array would fix that with random access, but it spends O(n) extra space that a purely pointer-based approach does not need.

The in-place approach chains three familiar linked list moves. First, locate the middle node using a fast and slow pointer, since the fast one reaches the end after the slow one has covered half the distance. Second, reverse the second half of the list starting right after the middle, so what was the tail becomes the head of that half. Third, merge the two halves by alternating one node from each in turn, the same way two sorted lists are merged, until one half runs out.

Solution

class ListNode {
  val: number;
  next: ListNode | null;
  constructor(val = 0, next: ListNode | null = null) {
    this.val = val;
    this.next = next;
  }
}

function reorderList(head: ListNode | null): void {
  if (head === null || head.next === null) {
    return;
  }

  // Find the middle of the list.
  let slow: ListNode = head;
  let fast: ListNode = head;
  while (fast.next !== null && fast.next.next !== null) {
    slow = slow.next as ListNode;
    fast = fast.next.next;
  }

  // Reverse the second half.
  let prev: ListNode | null = null;
  let curr: ListNode | null = slow.next;
  slow.next = null; // cut the first half so it doesn't tangle with the reversed second half
  while (curr !== null) {
    const next: ListNode | null = curr.next;
    curr.next = prev;
    prev = curr;
    curr = next;
  }

  // Merge the two halves by alternating nodes.
  let first: ListNode | null = head;
  let second: ListNode | null = prev;
  while (second !== null) { // second half is never longer, so it dictates when to stop
    const firstNext: ListNode | null = first!.next;
    const secondNext: ListNode | null = second.next;
    first!.next = second;
    second.next = firstNext;
    first = firstNext;
    second = secondNext;
  }
}

Complexity

Time: O(n). Three linear passes: one to find the middle, one to reverse, one to merge.
Space: O(1). Only a constant number of pointers are used; no auxiliary array or list.

Watch out for

The split point for an odd-length list leaves an extra node in the first half; the merge loop must account for unequal halves.
After splitting, the first half must have its tail pointer cut to null, or the two halves can accidentally form a cycle once merged.
Merge by alternating single nodes, stopping as soon as either half is exhausted.

Pattern

This problem is a composition of three independent linked-list primitives (find the middle, reverse a segment, merge two lists), each a pattern worth knowing on its own and frequently combined in harder list problems.

Reorder List