Reorder List Solution

Problem

Given a singly linked list, rearrange its nodes so that the first node is followed by the last node, then the second node, then the second-to-last node, and so on — interleaving from the outside in. The reordering must be done in-place without modifying node values.

→

→∅

[1,2,3,4,5]

After reordering:

→

→∅

[1,5,2,4,3]

Input: head = [1, 2, 3, 4, 5]
Output: [1, 5, 2, 4, 3]
Explanation: The last node (5) is inserted after the first (1), the second-to-last (4) after the second (2), and the middle (3) stays at the end.

A four-element list [1, 2, 3, 4] becomes [1, 4, 2, 3].

Intuition

The reordered list is the original first half interleaved with the reverse of the second half. If you split the list at its midpoint and reverse the back half, merging the two halves one node at a time gives exactly the required order.

Approach 1 — Array Conversion

Collect all node references into an array, then use two pointers advancing from opposite ends to rewire the .next pointers. Easy to reason about, but uses O(n) extra space.

Walk the list and append each node to an array.
Initialize left = 0 and right = len - 1 pointers.
While left < right, wire array[left].next = array[right] and array[right].next = array[left + 1].
Advance left forward and right backward.
Terminate the list by setting array[left].next = None.

1def reorderList(head):
2    if not head or not head.next:
3        return
4
5    nodes = []
6    current = head
7    while current:
8        nodes.append(current)
9        current = current.next
10
11    left, right = 0, len(nodes) - 1
12    while left < right:
13        nodes[left].next = nodes[right]   # wire outer-left to outer-right
14        nodes[right].next = nodes[left + 1]  # wire outer-right to next-left
15        left += 1
16        right -= 1
17
18    nodes[left].next = None  # terminate the merged list

Time: O(n) — one pass to collect nodes, one pass to rewire
Space: O(n) — the node array holds a reference to every node

Approach 2 — Find Middle + Reverse + Merge (In-Place)

Split the list at its midpoint, reverse the second half, then interleave the two halves. No extra data structure needed.

Use slow/fast pointers to find the midpoint (slow advances one step, fast two steps per iteration).
Sever the connection between the two halves (slow.next = None).
Reverse the second half in-place using the standard three-pointer technique.
Interleave: repeatedly take one node from the first half, then one from the reversed second half, until the second half is exhausted.

1def reorderList(head):
2    if not head or not head.next:
3        return
4
5    # Find the midpoint
6    slow, fast = head, head
7    while fast.next and fast.next.next:
8        slow = slow.next
9        fast = fast.next.next
10
11    # Reverse the second half
12    second_half = slow.next
13    slow.next = None  # disconnect the two halves
14    prev = None
15    current = second_half
16    while current:
17        next_node = current.next
18        current.next = prev
19        prev = current
20        current = next_node
21    second_half = prev  # head of the reversed second half
22
23    # Interleave the two halves
24    first_half = head
25    while second_half:
26        next_first = first_half.next
27        next_second = second_half.next
28        first_half.next = second_half
29        second_half.next = next_first  # insert second-half node between first-half nodes
30        first_half = next_first
31        second_half = next_second

Time: O(n) — three linear passes: find middle, reverse, merge
Space: O(1) — only a handful of pointer variables regardless of list length

Complexity Summary

Approach	Time	Space	When to use
Array Conversion	O(n)	O(n)	When clarity matters more than memory and the list is small
Find Middle + Reverse + Merge	O(n)	O(1)	Production code or interviews where in-place O(1) space is expected

Common Mistakes

Not severing the list before reversing. If you skip slow.next = None, the reversed second half still points back into the first half, creating a cycle that corrupts the merge step.
Off-by-one in finding the middle. Using while fast and fast.next instead of while fast.next and fast.next.next shifts the split point by one, giving the second half more nodes than intended and causing a null dereference during merge.
Reversing the first half instead of the second. The second half is reversed so that its tail (the true end of the list) connects naturally to the end of the first half during merging; reversing the wrong half scrambles the output order.
Forgetting to advance both pointers during merge. If you only advance first_half or second_half and not both, the loop runs forever or skips nodes.
Leaving a stale next pointer on the last merged node. When the second half has fewer nodes than the first (odd-length list), first_half ends up pointing to a leftover tail that was already correctly terminated — usually fine, but failing to set nodes[left].next = None in the array approach leaves a cycle.

Reorder List — Solution