Reorder List

You get the head of a singly linked list whose nodes, in order, are N0, N1, ..., Nn-1.

Rearrange the nodes so the list alternates between the front and the back: N0, Nn-1, N1, Nn-2, N2, Nn-3, ...

Do this by relinking the existing nodes; do not change any node's val and do not build new nodes. The function returns nothing: the judge reads the list starting from the original head. Lists are written as arrays of values, e.g. [10,20,30].

Example 1

Example 2

Example 3

Constraints

• 1 <= number of nodes <= 5 * 104
• 1 <= Node.val <= 1000

Pattern Path · Linked Lists · problem 76 of 169

Start simple

Copy every node into an array, then relink them with two indices moving inward: O(n) time but O(n) extra space; repeatedly walking to the current tail instead costs O(n²) time.

The key idea

Look at the target order as two sequences zipped together: the first half read forward (N0, N1, ...) and the second half read backward (Nn-1, Nn-2, ...). The only thing a singly linked list cannot give you cheaply is the backward walk, so create it by reversing the second half in place.

1. Find the middle with a slow pointer (one step) and a fast pointer (two steps). When fast cannot move further, slow is at the end of the first half. For odd lengths the first half keeps the extra middle node.
2. Cut and reverse: detach the second half by setting slow.next = null, then reverse it with the usual three-pointer loop.
3. Weave: take one node from the first half, then one from the reversed half, until the reversed half runs out.

Each step is a single linear pass and only a few pointers are kept, so the whole reordering is O(n) time with O(1) extra space.

Complexity

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

Python

class Solution:
    def reorderList(self, head):
        if head is None or head.next is None:
            return

        # 1. Find the end of the first half (it keeps the middle node for odd lengths).
        slow = fast = head
        while fast.next and fast.next.next:
            slow = slow.next
            fast = fast.next.next

        # 2. Detach the second half and reverse it.
        second = slow.next
        slow.next = None
        prev = None
        while second:
            nxt = second.next
            second.next = prev
            prev = second
            second = nxt
        second = prev

        # 3. Weave: one node from the front half, then one from the reversed back half.
        first = head
        while second:
            first_next, second_next = first.next, second.next
            first.next = second
            second.next = first_next
            first, second = first_next, second_next

JavaScript

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

  // 1. Find the end of the first half (it keeps the middle node for odd lengths).
  let slow = head, fast = head;
  while (fast.next && fast.next.next) {
    slow = slow.next;
    fast = fast.next.next;
  }

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

  // 3. Weave: one node from the front half, then one from the reversed back half.
  let first = head;
  while (second) {
    const firstNext = first.next, secondNext = second.next;
    first.next = second;
    second.next = firstNext;
    first = firstNext;
    second = secondNext;
  }
};

What the interviewer is checking

This combines three classic linked-list moves (middle finding, in-place reversal and merging), so it checks pointer discipline and whether you can decompose a problem into known building blocks.

Mistakes to avoid

• Not cutting the list at the middle, which leaves a cycle after merging.
• Off-by-one middle for even lengths, giving a first half that is too short.
• Losing the rest of a list by overwriting next before saving it during reversal or merging.
• Swapping values instead of relinking nodes, which the problem forbids.

Follow-ups to expect

• Can you do it recursively? (Yes, but O(n) stack depth.)
• How would you undo the reordering? (Unweave, reverse second half, append.)
• What about a doubly linked list? (No reversal needed; walk from tail.)

In real software

Interleaving the front and back of a sequence shows up when balancing a playlist or a task queue so that oldest and newest items alternate, and the same pointer surgery is used inside memory allocators that splice free lists.

Practice next