Reorder List

Difficulty: Medium

Problem

You are given the head of a singly linked list:

L0 → L1 → … → Ln-1 → Ln

Reorder the list to be:

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.

Example

Input: head = [1,2,3,4,5]
Output: [1,5,2,4,3]
Explanation: Reorder by interleaving from both ends: first, last, second, second-last, middle.

Brute-force approach — Store Nodes in Array, Reorder by Index

Store all nodes in an array, then rebuild the list by picking from both ends alternately: index 0, n-1, 1, n-2, etc.

Steps

  1. Traverse list, store all nodes in an array
  2. Use two pointers: left = 0, right = n-1
  3. Alternate: pick left, pick right, move both inward
  4. Set the last node's next to null
  5. Return the reordered list

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

Trade-offs

  • Requires an additional array of size n
  • Not truly in-place manipulation

Optimal approach — Find Middle → Reverse → Merge

Key insight: Decompose into 3 known sub-problems: find middle, reverse list, merge two lists.

Split into 3 sub-problems: find the middle with slow/fast pointers, reverse the second half in-place, then merge the two halves alternately. No extra space needed.

Steps

  1. Find middle using slow/fast pointers
  2. Reverse the second half of the list
  3. Merge both halves alternately

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