Reorder List

Difficulty: Medium

Problem

You are given the head of a singly linked list whose nodes, in order, are first, second, third, and so on up to last. Rearrange the nodes so the list reads: first, last, second, second-to-last, third, third-to-last, and so on, alternating between the front and the back until every node has been used.

You may not change the values stored in the nodes. Only the nodes themselves may be relinked.

Example

Input: head = [1,2,3,4,5,6]
Output: [1,6,2,5,3,4]
Explanation: Alternate between the two ends: 1 (first), 6 (last), 2 (second), 5 (second-last), 3, then 4.

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)

Pseudocode

function reorderList(head):
    // Find middle
    slow = head; fast = head
    while fast.next AND fast.next.next:
        slow = slow.next; fast = fast.next.next
    // Reverse second half
    prev = null; curr = slow.next
    slow.next = null
    while curr:
        next = curr.next; curr.next = prev
        prev = curr; curr = next
    // Merge two halves
    first = head; second = prev
    while second:
        tmp1 = first.next; tmp2 = second.next
        first.next = second; second.next = tmp1
        first = tmp1; second = tmp2

Hints

  • Split the problem into 3 sub-problems
  • Find the middle using slow/fast pointers
  • Reverse the second half, then merge alternately

Complexity questions

What is the time complexity of the array-based approach?

O(n). We traverse the list once to build the array and once to reorder, giving O(n).

What is the space complexity of the array-based approach?

O(n). We store all n nodes in an array, requiring O(n) space.

What is the time complexity of the three-step in-place approach?

O(n). Finding middle is O(n), reversing is O(n/2), merging is O(n/2). Total: O(n).

What is the space complexity of the three-step approach?

O(1). All operations are done in-place using only pointer manipulation, giving O(1) space.

Check your understanding of Reorder List

For list [1,2,3,4], what is the reordered result?

[1,4,2,3]. Reorder interleaves from the front and back: first (1), last (4), second (2), second-to-last (3) → [1,4,2,3].

For list [1,2,3,4,5], what is the reordered result?

[1,5,2,4,3]. The pattern is: first, last, second, second-to-last, middle. So [1,2,3,4,5] becomes [1,5,2,4,3].

What happens with a list of 1 or 2 nodes?

The list stays the same, it's already in reorder form. A single node [1] or two nodes [1,2] are already in the correct reorder form, so no changes needed.

Related problems

Keep practising