Module 11 · Linked Lists and Pointer Mutation

109. Reorder List

Interview · Download this solution · All solutions and shared helpers

Problem

Reorder a finite singly linked list from L0,L1,...,Ln to L0,Ln,L1,Ln-1,... by changing links rather than values. Return the original head reference, now heading the reordered chain. Empty and singleton chains are unchanged.

Examples

Example 1

list_values(reorder_list(build_list([1,2,3,4,5])))
=> [1, 5, 2, 4, 3]

An odd-length first half has one final unpaired node.

Example 2

list_values(reorder_list(build_list([1,2,3,4])))
=> [1, 4, 2, 3]

Even halves weave completely.

Example 3

reorder_list(None)
=> None

The empty chain is unchanged.

Reveal the worked solution and reasoning

Why this mechanism works

The requested order alternates a forward traversal of the first half with a backward traversal of the second. Split the chain, reverse the second half, then weave the two lists. Severing the split link before weaving prevents the old connection from creating a cycle.

State and boundaries

slow locates the first-half tail. second is the reversed second-half head. During weaving, first and second name the next unconsumed nodes of their respective halves.

Protocol

Locate the midpoint with slow/fast pointers.
Cut after slow.
Reverse the detached second half.
Alternately link one node from each half, saving both next pointers first.
Return head.

Visualization

1->2->3 | 4->5
reverse second: 5->4
weave: 1->5->2->4->3

Python implementation

from structures import build_list, list_values

def reorder_list(head):
    if head is None or head.next is None:
        return head
    slow, fast = head, head.next
    while fast is not None and fast.next is not None:
        slow = slow.next
        fast = fast.next.next
    current = slow.next
    slow.next = None
    second = None
    while current is not None:
        following = current.next
        current.next = second
        second, current = current, following
    first = head
    while second is not None:
        next_first, next_second = first.next, second.next
        first.next = second
        second.next = next_first
        first, second = next_first, next_second
    return head

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

list_values(reorder_list(build_list([1,2,3,4,5])))

L4 reorder_list: if head is None or head.next is None:
head=N1(val=1,next=N2,random=None)

L6 reorder_list: slow, fast = head, head.next
head=N1(val=1,next=N2,random=None); slow=N1(val=1,next=N2,random=None); fast=N2(val=2,next=N3,random=None)

L8 reorder_list: slow = slow.next
head=N1(val=1,next=N2,random=None); slow=N2(val=2,next=N3,random=None); fast=N2(val=2,next=N3,random=None)

L9 reorder_list: fast = fast.next.next
head=N1(val=1,next=N2,random=None); slow=N2(val=2,next=N3,random=None); fast=N4(val=4,next=N5,random=None)

L8 reorder_list: slow = slow.next
head=N1(val=1,next=N2,random=None); slow=N3(val=3,next=N4,random=None); fast=N4(val=4,next=N5,random=None)

L9 reorder_list: fast = fast.next.next
head=N1(val=1,next=N2,random=None); slow=N3(val=3,next=N4,random=None); fast=None

L10 reorder_list: current = slow.next
head=N1(val=1,next=N2,random=None); slow=N3(val=3,next=N4,random=None); fast=None; current=N4(val=4,next=N5,random=None)

L11 reorder_list: slow.next = None
head=N1(val=1,next=N2,random=None); slow=N3(val=3,next=None,random=None); fast=None; current=N4(val=4,next=N5,random=None)

... 12 intermediate state changes omitted ...

L19 reorder_list: next_first, next_second = first.next, second.next
head=N1(val=1,next=N5,random=None); slow=N3(val=3,next=None,random=None); fast=None; current=None; second=N4(val=4,next=None,random=None); following=None; first=N2(val=2,next=N3,random=None); next_first=N3(val=3,next=None,random=None); next_second=None

L20 reorder_list: first.next = second
head=N1(val=1,next=N5,random=None); slow=N3(val=3,next=None,random=None); fast=None; current=None; second=N4(val=4,next=None,random=None); following=None; first=N2(val=2,next=N4,random=None); next_first=N3(val=3,next=None,random=None); next_second=None

L21 reorder_list: second.next = next_first
head=N1(val=1,next=N5,random=None); slow=N3(val=3,next=None,random=None); fast=None; current=None; second=N4(val=4,next=N3,random=None); following=None; first=N2(val=2,next=N4,random=None); next_first=N3(val=3,next=None,random=None); next_second=None

L22 reorder_list: first, second = next_first, next_second
head=N1(val=1,next=N5,random=None); slow=N3(val=3,next=None,random=None); fast=None; current=None; second=None; following=None; first=N3(val=3,next=None,random=None); next_first=N3(val=3,next=None,random=None); next_second=None

Result: [1, 5, 2, 4, 3]. An odd-length first half has one final unpaired node.

list_values(reorder_list(build_list([1,2,3,4])))

L4 reorder_list: if head is None or head.next is None:
head=N1(val=1,next=N2,random=None)

L6 reorder_list: slow, fast = head, head.next
head=N1(val=1,next=N2,random=None); slow=N1(val=1,next=N2,random=None); fast=N2(val=2,next=N3,random=None)

L8 reorder_list: slow = slow.next
head=N1(val=1,next=N2,random=None); slow=N2(val=2,next=N3,random=None); fast=N2(val=2,next=N3,random=None)

L9 reorder_list: fast = fast.next.next
head=N1(val=1,next=N2,random=None); slow=N2(val=2,next=N3,random=None); fast=N4(val=4,next=None,random=None)

L10 reorder_list: current = slow.next
head=N1(val=1,next=N2,random=None); slow=N2(val=2,next=N3,random=None); fast=N4(val=4,next=None,random=None); current=N3(val=3,next=N4,random=None)

L11 reorder_list: slow.next = None
head=N1(val=1,next=N2,random=None); slow=N2(val=2,next=None,random=None); fast=N4(val=4,next=None,random=None); current=N3(val=3,next=N4,random=None)

L12 reorder_list: second = None
head=N1(val=1,next=N2,random=None); slow=N2(val=2,next=None,random=None); fast=N4(val=4,next=None,random=None); current=N3(val=3,next=N4,random=None); second=None

L14 reorder_list: following = current.next
head=N1(val=1,next=N2,random=None); slow=N2(val=2,next=None,random=None); fast=N4(val=4,next=None,random=None); current=N3(val=3,next=N4,random=None); second=None; following=N4(val=4,next=None,random=None)

... 9 intermediate state changes omitted ...

L22 reorder_list: first, second = next_first, next_second
head=N1(val=1,next=N4,random=None); slow=N2(val=2,next=None,random=None); fast=N4(val=4,next=N2,random=None); current=None; second=N3(val=3,next=None,random=None); following=None; first=N2(val=2,next=None,random=None); next_first=N2(val=2,next=None,random=None); next_second=N3(val=3,next=None,random=None)

L19 reorder_list: next_first, next_second = first.next, second.next
head=N1(val=1,next=N4,random=None); slow=N2(val=2,next=None,random=None); fast=N4(val=4,next=N2,random=None); current=None; second=N3(val=3,next=None,random=None); following=None; first=N2(val=2,next=None,random=None); next_first=None; next_second=None

L20 reorder_list: first.next = second
head=N1(val=1,next=N4,random=None); slow=N2(val=2,next=N3,random=None); fast=N4(val=4,next=N2,random=None); current=None; second=N3(val=3,next=None,random=None); following=None; first=N2(val=2,next=N3,random=None); next_first=None; next_second=None

L22 reorder_list: first, second = next_first, next_second
head=N1(val=1,next=N4,random=None); slow=N2(val=2,next=N3,random=None); fast=N4(val=4,next=N2,random=None); current=None; second=None; following=None; first=None; next_first=None; next_second=None

Result: [1, 4, 2, 3]. Even halves weave completely.

Why the solution is correct

The split gives the first half at least as many nodes as the second. Reversal makes the second half appear in the needed end-to-middle order. Each weave step commits the next required pair and preserves both unread suffixes, so all nodes appear once without a cycle.

Time and space

O(n) time across three linear phases and O(1) auxiliary space.

Common mistakes

Leaving the midpoint connection intact can create a cycle. Overwriting a next link before saving both suffixes can lose remaining nodes.

Reasoning card

State: slow locates the first-half tail. second is the reversed second-half head. During weaving, first and second name the next unconsumed nodes of their respective halves.

Invariant: Each phase has a separate structural invariant.

Decision to rehearse: Find middle, reverse second half, merge alternating nodes.

Finish: Return head

Transfer exercise

Write a structural test that checks node identity preservation, absence of cycles and the final value order independently.