DSA Reordering a List

The problem

Reorder List rewrites a linked list as first, last, second, second last, and so on. The chain keeps its own nodes. Only the links between them change.

The cases below are the ones this article tests every solution against. They cover odd and even lengths, and the shortest chains.

cases = [
    ([1, 2, 3, 4, 5], [1, 5, 2, 4, 3]),
    ([1, 2, 3, 4], [1, 4, 2, 3]),
    ([1, 2, 3], [1, 3, 2]),
    ([1], [1]),
]
for values, expected in cases:
    print("before:", values, "after:", expected)

Read the first row slowly. The order takes the head, then the tail, then the second node, then the second last. The middle value of an odd list, 3 in the first row, ends the chain.

Intuition: pick from both ends of a row

The first idea lays the values out in a row and picks from alternate ends. Left, right, left, right. The picking pattern is easy to see in a plain list.

A linked list has no right end to pick from. Reaching the tail means walking the whole chain, and the row of values exists only because a Python list stored it. That storage is the cost the real solution avoids.

values = [1, 2, 3, 4, 5]
out = []
lo = 0
hi = len(values) - 1
while lo <= hi:
    out.append(values[lo])
    lo += 1
    if lo <= hi:
        out.append(values[hi])
        hi -= 1
print("picked order:", out)
print("values stored in a row first:", len(values))

The pattern is right and the machinery is wrong for a chain. The optimal solution rebuilds the same pattern from three chain moves. The brute force first keeps the row, so its cost can be counted.

Brute force: collect the nodes, then relink

The brute force walks the chain once and collects every node into a list. It then relinks the nodes in picked order, taking from the front and the back of that list in turn. The chain's own nodes are reused, and the collected list is the extra memory.

class Node:
    def __init__(self, value):
        self.value = value
        self.next = None

def build(values):
    nodes = [Node(v) for v in values]
    for i in range(len(nodes) - 1):
        nodes[i].next = nodes[i + 1]
    return (nodes[0] if nodes else None), nodes

def to_list(head):
    out = []
    node = head
    while node is not None:
        out.append(node.value)
        node = node.next
    return out

def reorder_collect(head):
    nodes = []
    node = head
    while node is not None:
        nodes.append(node)
        node = node.next
    if not nodes:
        return None, 0
    order = []
    lo = 0
    hi = len(nodes) - 1
    while lo <= hi:
        order.append(nodes[lo])
        lo += 1
        if lo <= hi:
            order.append(nodes[hi])
            hi -= 1
    for i in range(len(order) - 1):
        order[i].next = order[i + 1]
    order[-1].next = None
    return order[0], len(nodes)

for values in [[1, 2, 3, 4, 5], [1, 2, 3, 4]]:
    head, nodes = build(values)
    new_head, stored = reorder_collect(head)
    print("before:", values, "after:", to_list(new_head), "nodes stored:", stored)

Five nodes meant five stored references. The count grows one for one with the chain. A chain too long for memory fails here even though the answer itself needs no new nodes at all.

The optimal solution: cut, reverse, weave

Weaving means taking one node from each of two chains in turn, and the whole reorder is three moves composed: find the middle and cut the chain there, reverse the second half in place, then weave the two halves together. That one sentence is the full method.

Reversing a chain in place points each link back at the node before it. The first half is never shorter than the second half, so the weave always runs out of second-half nodes first, which ends the chain cleanly.

class Node:
    def __init__(self, value):
        self.value = value
        self.next = None

def build(values):
    nodes = [Node(v) for v in values]
    for i in range(len(nodes) - 1):
        nodes[i].next = nodes[i + 1]
    return (nodes[0] if nodes else None), nodes

def to_list(head):
    out = []
    node = head
    while node is not None:
        out.append(node.value)
        node = node.next
    return out

def reorder(head):
    if head is None or head.next is None:
        return head
    slow = head
    fast = head
    while fast.next is not None and fast.next.next is not None:
        slow = slow.next
        fast = fast.next.next
    second = slow.next
    slow.next = None
    prev = None
    node = second
    while node is not None:
        nxt = node.next
        node.next = prev
        prev = node
        node = nxt
    second = prev
    first = head
    while second is not None:
        next_first = first.next
        next_second = second.next
        first.next = second
        second.next = next_first
        first = next_first
        second = next_second
    return head

cases = [
    ([1, 2, 3, 4, 5], [1, 5, 2, 4, 3]),
    ([1, 2, 3, 4], [1, 4, 2, 3]),
    ([1, 2, 3], [1, 3, 2]),
    ([1], [1]),
]
for values, expected in cases:
    head, nodes = build(values)
    result = to_list(reorder(head))
    print("before:", values, "after:", result, "expected:", expected, "match:", result == expected)

All four cases from the start of the article pass. No list of nodes is built anywhere in the code. The only extra storage is a handful of node references.

Walkthrough: [1, 2, 3, 4, 5] through the three moves

The walk runs the three moves one at a time on the first case. The chain is printed after the cut, after the reversal, and after each weave step. The remaining second half is printed beside the woven chain while weaving lasts.

class Node:
    def __init__(self, value):
        self.value = value
        self.next = None

def build(values):
    nodes = [Node(v) for v in values]
    for i in range(len(nodes) - 1):
        nodes[i].next = nodes[i + 1]
    return (nodes[0] if nodes else None), nodes

def to_list(head):
    out = []
    node = head
    while node is not None:
        out.append(node.value)
        node = node.next
    return out

head, nodes = build([1, 2, 3, 4, 5])
slow = head
fast = head
while fast.next is not None and fast.next.next is not None:
    slow = slow.next
    fast = fast.next.next
second = slow.next
slow.next = None
print("after the cut - first half:", to_list(head), "second half:", to_list(second))
prev = None
node = second
while node is not None:
    nxt = node.next
    node.next = prev
    prev = node
    node = nxt
second = prev
print("after the reversal - second half:", to_list(second))
first = head
step = 0
while second is not None:
    step += 1
    next_first = first.next
    next_second = second.next
    first.next = second
    second.next = next_first
    first = next_first
    second = next_second
    print("weave step", step, "- chain so far:", to_list(head), "second half left:", to_list(second))
print("final chain:", to_list(head))

The cut leaves the middle node, 3, at the end of the first half. The reversal turns 4, 5 into 5, 4. Two weave steps spend the second half, and the chain reads 1, 5, 2, 4, 3, exactly the target order.

Complexity

Both versions walk the chain a fixed number of times, so both take O(n) time for n nodes. Cutting, reversing, and weaving are one walk each, and a constant number of walks is still linear.

The collect version stores n node references, so its extra space is O(n). The three-move version stores a constant number of references, so its extra space is O(1).

for n in [5, 10, 20]:
    print("nodes:", n, "collect version references stored:", n, "three-move references stored: 4")

The three-move count never moves. Four references, the two runners and the two weave pointers, serve a chain of any length. That flat line is the whole gain over collecting.

Edge cases and pitfalls

Forgetting to cut the chain before reversing is the classic bug. The second half then still hangs off the first half, and the weave chases links back into nodes it already placed. The cut, one link set to None, is what makes the two halves separate chains.

An even-length chain splits into two equal halves. An odd-length chain leaves the extra node in the first half, where it correctly ends the woven chain.

class Node:
    def __init__(self, value):
        self.value = value
        self.next = None

def build(values):
    nodes = [Node(v) for v in values]
    for i in range(len(nodes) - 1):
        nodes[i].next = nodes[i + 1]
    return (nodes[0] if nodes else None), nodes

def to_list(head):
    out = []
    node = head
    while node is not None:
        out.append(node.value)
        node = node.next
    return out

def reorder(head):
    if head is None or head.next is None:
        return head
    slow = head
    fast = head
    while fast.next is not None and fast.next.next is not None:
        slow = slow.next
        fast = fast.next.next
    second = slow.next
    slow.next = None
    prev = None
    node = second
    while node is not None:
        nxt = node.next
        node.next = prev
        prev = node
        node = nxt
    second = prev
    first = head
    while second is not None:
        next_first = first.next
        next_second = second.next
        first.next = second
        second.next = next_first
        first = next_first
        second = next_second
    return head

for values in [[], [1], [1, 2], [1, 2, 3], [1, 2, 3, 4, 5, 6]]:
    head, nodes = build(values)
    print("before:", values, "after:", to_list(reorder(head)))

Two nodes survive unchanged, because first-then-last on a pair is the pair itself. The empty chain returns None through the same guard that handles a single node. No case needs its own branch.