Reorder List · DSA Prep

The target order interleaves the list with itself reversed: first-from-front, first-from-back, second-from-front, second-from-back, and so on. That “zip from both ends” shape is easy to produce with an array, but the optimal approach gets there using only pointer rewrites: split the list in half, reverse the second half, then merge the two halves alternately.

Copy Into an Array

Time O(n)Space O(n)

Dump every node into a list, then use two indices — one starting at the front, one at the back — to rewire next pointers in the zigzag order directly from the array. This is easy to get right, but it needs O(n) extra space to hold the array of node references.

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution:
    def reorderList(self, head: ListNode | None) -> None:
        nodes = []
        node = head
        while node:
            nodes.append(node)
            node = node.next

        lo, hi = 0, len(nodes) - 1
        while lo < hi:
            nodes[lo].next = nodes[hi]
            lo += 1
            if lo == hi:
                break
            nodes[hi].next = nodes[lo]
            hi -= 1
        nodes[lo].next = None

Correct and straightforward, but every node reference is duplicated into the array — unnecessary, since the nodes and their relative order already exist in the list itself.

Split, Reverse, Merge In-Place

OptimalTime O(n)Space O(1)

Three pointer-only steps, no extra storage:

Find the middle of the list with the slow/fast pointer trick, and split it into a front half and a back half.
Reverse the back half in place (same technique as reversing a whole list).
Merge the two halves by alternating nodes: one from the front half, one from the reversed back half, repeat.

class Solution:
    def reorderList(self, head: ListNode | None) -> None:
        if not head or not head.next:
            return

        # 1. Find the middle (slow ends on the last node of the front half)
        slow, fast = head, head
        while fast.next and fast.next.next:
            slow = slow.next
            fast = fast.next.next

        # 2. Reverse the second half
        second = slow.next
        slow.next = None   # cut the list into two halves
        prev = None
        while second:
            next_node = second.next
            second.next = prev
            prev = second
            second = next_node

        # 3. Merge the two halves alternately
        first, second = head, prev
        while second:
            first_next, second_next = first.next, second.next
            first.next = second
            second.next = first_next
            first, second = first_next, second_next

Tracing head = [1,2,3,4,5] — after finding the middle (node 3) and reversing the back half (4→5 becomes 5→4), the merge step alternates front and reversed-back nodes:

▲first

▲second

1 / 3

After split + reverse: front half is 1→2→3, reversed back half is 5→4 (drawn separately). Begin merging.

Why it’s correct: after the split, the front half holds L0..Lk in order and the reversed back half holds Ln..Lk+1 in order — interleaving them one at a time produces exactly L0, Ln, L1, Ln-1, ..., matching the required pattern. Complexity: finding the middle, reversing, and merging are each a single O(n) pass over the list, with only a constant number of pointer variables → O(n) time, O(1) space — this is optimal, since every node’s next pointer must be touched at least once to reorder the list.