Reorder List

Problem

Given the head of a singly linked list L0 → L1 → … → L(n-1), rearrange its nodes in place into the interleaved order:

L0 → L(n-1) → L1 → L(n-2) → L2 → L(n-3) → …

That is, alternate between the front of the list and the back of the list, working inward. Only node links may be changed — you may not rewrite node values. The function returns nothing; it mutates the list.

Examples

• Input: head = [1, 2, 3, 4] → List becomes [1, 4, 2, 3] Front 1, back 4, front 2, back 3.
• Input: head = [1, 2, 3, 4, 5] → List becomes [1, 5, 2, 4, 3] Front 1, back 5, front 2, back 4, and the middle 3 lands last.
• Input: head = [7, 9] → List becomes [7, 9] Two nodes are already in reordered form.

Constraints

• 1 <= n <= 5 * 10^4 where n is the number of nodes.
• 1 <= Node.val <= 1000.

At 5·10^4 nodes, repeatedly walking to the current tail (O(n²)) is on the edge; the intended solution is O(n) time, and the classic follow-up is O(1) extra space.

Think about it first

TL;DR

Find middle + reverse second half + alternate merge — O(n) time, O(1) space.

Approach 1 — Brute force: array of nodes, two indices

Load every node into a Python list; then left and right indices walking inward give the exact output order, and you relink as you go.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

def reorderList(head: Optional[ListNode]) -> None:
    nodes: List[ListNode] = []
    node = head
    while node:
        nodes.append(node)
        node = node.next
    left, right = 0, len(nodes) - 1
    while left < right:
        nodes[left].next = nodes[right]
        left += 1
        if left == right:
            break
        nodes[right].next = nodes[left]
        right -= 1
    nodes[left].next = None

Time O(n), space O(n). This passes the time limit but uses O(n) extra space, so it fails the follow-up’s O(1) space requirement — the improvement an interviewer will ask for next.

Approach 2 — Middle + reverse + merge (optimal)

The target order is the first half interleaved with the reversed second half. Each part is a standard routine: a slow/fast pointer scan to find the middle (fast advances two nodes for every one of slow, so slow stops midway), an in-place reversal (flip each next pointer), and an alternating merge of two lists. Together they solve the problem in three linear passes with no extra storage.

flowchart TD
    A["1 → 2 → 3 → 4 → 5"] -->|find middle| B["first: 1 → 2 → 3<br/>second: 4 → 5"]
    B -->|reverse second half| C["first: 1 → 2 → 3<br/>second: 5 → 4"]
    C -->|merge alternately| D["1 → 5 → 2 → 4 → 3"]

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

def reorderList(head: Optional[ListNode]) -> None:
    # 1. find the middle: slow ends at the last node of the first half
    slow, fast = head, head.next
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next

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

    # 3. merge alternately: first half is never shorter than second
    first, second = head, prev
    while second:
        f_next, s_next = first.next, second.next
        first.next = second
        second.next = f_next
        first, second = f_next, s_next

Walkthrough on [1, 2, 3, 4, 5]:

1. Middle: with fast = head.next, slow stops at 3 → first half 1→2→3, second half 4→5.
2. Detach and reverse: second half becomes 5→4.
3. Merge, one row per loop iteration:

second is exhausted; the leftover middle node 3 is already correctly at the tail. Result [1, 5, 2, 4, 3].

Time O(n): three linear passes. Space O(1): a fixed number of pointers.

Starting fast at head.next makes slow stop at ceil(n/2), so for odd n the extra node stays in the first half — that is what lets the merge loop terminate purely on second.

Approach 3 — Recursion on the outer pair

A recursive framing: reorder the sublist strictly inside head and the tail, then splice head → tail → (reordered inner part). Finding the tail directly each time costs O(n), giving O(n²); the recursive variant below uses the call stack to walk backward instead.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

def reorderList(head: Optional[ListNode]) -> None:
    front = head
    stop = False

    def visit(node: Optional[ListNode]) -> None:
        nonlocal front, stop
        if not node:
            return
        visit(node.next)          # unwind from the tail backward
        if stop:
            return
        if front is node or front.next is node:
            node.next = None      # middle reached: terminate list
            stop = True
            return
        nxt = front.next          # weave: front -> node -> old front.next
        front.next = node
        node.next = nxt
        front = nxt

    visit(head)

Walkthrough on [1, 2, 3, 4]: the recursion bottoms out at 4 and unwinds. Visiting 4: weave after front 1 → 1→4→2→3, front becomes 2. Visiting 3: front.next is node (2’s next is 3) → set 3.next = None, stop. Result [1, 4, 2, 3].

Time O(n), space O(n) for the recursion stack. With up to 5·10^4 nodes this overflows Python’s default recursion limit, so the iterative Approach 2 is the safer answer.

Common pitfalls

• Forgetting slow.next = None before reversing — the first half then still runs into the second and the merge loops forever or duplicates nodes.
• Off-by-one in the middle finder: fast = head.next vs fast = head changes which half gets the odd middle node; the merge termination condition must match your choice.
• Losing first.next / second.next before overwriting them in the merge — save both, then splice.
• Rewriting node values from an array instead of relinking nodes — explicitly against the problem statement.

Pattern takeaway

Reorder List combines three standard linked-list routines: finding the middle, reversing in place, and merging. The skill is recognizing that a complex-looking permutation decomposes into operations you already know. When a target order mixes forward-from-the-front with backward-from-the-back, split at the middle, reverse one side, and merge.