medium

Reorder List

Reorder a linked list by weaving its first half with its reversed second half.

1. Define the problem

Reorder List

You are given the values of the nodes of a singly linked list L0 -> L1 -> ... -> Ln-1 -> Ln. Reorder the list to be on the following form: L0 -> Ln -> L1 -> Ln-1 -> L2 -> Ln-2 -> ... You may not modify the values in the list's nodes. Only nodes themselves may be changed. Find the middle with fast and slow pointers , reverse the second half, then weave-merge the two halves alternately .

Constraints

  • The number of nodes in the list is in the range [1, 5 × 104].
  • 1 ≤ valuesi ≤ 1000

Example

Inputvalues = [1, 2, 3, 4]
Output[1, 4, 2, 3]

Explanation Splitting the list into [1,2] and [3,4], reversing the second half to [4,3], and weaving them alternately gives 1 -> 4 -> 2 -> 3.

2. Know the words first

In plain terms

Linked list
A chain of nodes where each node just points to the next one, unlike an array where all the values sit together in one contiguous block.
3. Visualize the solution

Find the middle, reverse the second half, then weave-merge

Find the middle, reverse the second half, then weave-merge
Statusinit

slow and fast both start at index 0 (value 1).

What happens in this step

values = [1, 2, 3, 4]
slow = 0, fast = 0

Loop condition: "while fast.next && fast.next.next" — fast still has
two more nodes ahead, so the loop runs.
Step 1 of 4

Steps to visualize

  1. Use fast and slow pointers to find the middle node of the list.
  2. Split the list into two halves at the middle.
  3. Reverse the second half in place.
  4. Weave the two halves together, alternating one node from each.
  5. Walk the final list to read off the reordered values.
4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

Find the middle, reverse the second half, then weave-merge
Statusinit

slow and fast both start at index 0 (value 1).

What happens in this step

values = [1, 2, 3, 4]
slow = 0, fast = 0

Loop condition: "while fast.next && fast.next.next" — fast still has
two more nodes ahead, so the loop runs.
Step 1 of 4
5. Solution

Solution

solution.tsTypeScript
function reorderList(values) {
  if (values.length === 0) {
    return [];
  }

  const nodes = values.map((val) => ({ val, next: null }));
  for (let i = 0; i < nodes.length - 1; i++) {
    nodes[i].next = nodes[i + 1];
  }

  let slow = nodes[0];
  let fast = nodes[0];
  while (fast.next !== null && fast.next.next !== null) {
    slow = slow.next;
    fast = fast.next.next;
  }

  let second = slow.next;
  slow.next = null;
  let prev = null;
  while (second !== null) {
    const next = second.next;
    second.next = prev;
    prev = second;
    second = next;
  }
  second = prev;

  let first = nodes[0];
  while (second !== null) {
    const firstNext = first.next;
    const secondNext = second.next;
    first.next = second;
    second.next = firstNext;
    first = firstNext;
    second = secondNext;
  }

  const result = [];
  let node = nodes[0];
  while (node !== null) {
    result.push(node.val);
    node = node.next;
  }

  return result;
}
Time
O(n)
Space
O(1) (excluding the constructed list and result array)
6. Test cases

Test cases

InputExpectedCovers
values = [1, 2, 3, 4][1, 4, 2, 3]example from the docstring, even length
values = [1, 2, 3, 4, 5][1, 5, 2, 4, 3]odd-length list with a single true middle node
values = [1, 2][1, 2]smallest interesting case: only two nodes
values = [1][1]smallest valid input: a single node
values = [1, 2, 3, 4, 5, 6][1, 6, 2, 5, 3, 4]a larger even-length list
values = [2, 2, 2, 2][2, 2, 2, 2]every node holding the same value

Keep reading