Reorder List

Some list problems are new ideas. This one is not. It is three routines you already have, run one after another, and the skill it tests is seeing that. Candidates who try to solve it directly get lost in pointer bookkeeping; candidates who name the three steps usually finish in fifteen minutes.

It also contains the most instructive bug in this section. Forget one line — the cut between the two halves — and the program does not return a wrong answer. It never returns at all.

The problem

You are given the head of a list L0 → L1 → … → Ln−1 → Ln. Rearrange its nodes, in place, into L0 → Ln → L1 → Ln−1 → L2 → …: first node, last node, second node, second-to-last node, and so on. Return nothing; the list is changed in place.

• 1 → 2 → 3 → 4 → 5 → 1 → 5 → 2 → 4 → 3.
• 1 → 2 → 3 → 4 → 5 → 6 → 1 → 6 → 2 → 5 → 3 → 4.

Constraints: 1 to 5 × 10⁴ nodes. Move the nodes; do not change their values.

Clarifying questions

• In place, or can I return a new list? In place, moving the existing nodes.
• Can I swap values instead of nodes? No.
• What about one or two nodes? They are already in the required order; do nothing.
• Is O(n) extra space acceptable? It is a fine first answer; the follow-up asks for O(1).

Approach 1: an array of nodes, relinked from both ends

The difficulty is reaching the last nodes, which a singly linked list cannot do cheaply. An array of the nodes fixes that: index both ends and relink.

1def reorder_list_array(head: ListNode | None) -> None:2    """Put the nodes in an array, then relink from both ends. O(n) space."""3    nodes = []4    while head is not None:5        nodes.append(head)6        head = head.next7    left, right = 0, len(nodes) - 18    while left < right:9        nodes[left].next = nodes[right]10        left += 111        if left == right:12            break13        nodes[right].next = nodes[left]14        right -= 115    if nodes:16        nodes[left].next = None          # the last node placed ends the list

Time: O(n). Space: O(n) for the array.

This is a correct, clear answer, and it relinks real nodes rather than values. Its only weakness is the O(n) array — for 5 × 10⁴ nodes, 5 × 10⁴ references. When the interviewer asks for O(1) extra space, the array has to go, and with it the ability to reach the end directly.

The key insight

Look at the target order as two sequences, zipped: the front half in order (L0, L1, L2, …) and the back half in reverse (Ln, Ln−1, …). A singly linked list can easily walk forward, but not backward. So make the back half walk forward: reverse it.

That gives three steps, each one a routine from this course:

1. Find the middle and cut the list into a front half and a back half. (Slow and fast pointers — the Fast and Slow Pointers section covers why it works.)
2. Reverse the back half with the three-pointer loop from Reverse Linked List.
3. Interleave the two halves, one node from each in turn — a merge that alternates instead of comparing.

The front half gets the extra node when the length is odd. With fast.next and fast.next.next as the loop condition, slow stops on the last node of the front half: node 3 for both 5 and 6 nodes.

Does the exact middle matter? Less than you might fear. The other common loop, while fast is not None and fast.next is not None, stops slow on node 4 of a 6-node list, so the front half is 1 → 2 → 3 → 4 and the back is 5 → 6. The interleave then produces 1 → 6 → 2 → 5 → 3 → 4 — the same answer, because the front half's extra node simply stays at the end. We checked both conventions on lists of 0 to 11 nodes. What does matter is that the back half is never longer than the front, and that the two halves are cut apart.

Approach 2: middle, reverse, interleave

1def reorder_list(head: ListNode | None) -> None:2    """Find the middle, reverse the back half, then zip the halves together."""3    if head is None or head.next is None:4        return5    slow = fast = head                   # 1. slow stops at the end of the front half6    while fast.next is not None and fast.next.next is not None:7        slow = slow.next8        fast = fast.next.next9    second = slow.next                   # 2. cut, then reverse the back half10    slow.next = None11    previous = None12    while second is not None:13        next_node = second.next14        second.next = previous15        previous = second16        second = next_node17    first, second = head, previous       # 3. interleave18    while second is not None:19        first_next, second_next = first.next, second.next20        first.next = second21        second.next = first_next22        first, second = first_next, second_next

In step 3, both next pointers are saved before either is overwritten — the same "save before you flip" rule. The loop runs while the back half has nodes; since the front half is the same length or one longer, first never runs out first.

Dry run on 1 → 2 → 3 → 4 → 5 → 6:

On 1 → 2 → 3 → 4 → 5, slow also stops on 3; the front is 1 → 2 → 3, the reversed back is 5 → 4, and two interleave steps give 1 → 5 → 2 → 3 and then 1 → 5 → 2 → 4 → 3. Node 3 was already cut from the back half, so it correctly ends the list.

Time: O(n) — three passes over at most n nodes each. Space: O(1) — a handful of pointers.

Edge cases

• One or two nodes: the early return. (Running the full algorithm on two nodes also works, but the guard makes it obvious.)
• Three nodes: 1 → 2 → 3 → 1 → 3 → 2. The front is 1 → 2, the back is 3.
• Odd length: the middle node stays at the end of the front half and ends the final list.
• Missing cut: without slow.next = None, node 3 still points at node 4, and interleaving builds a cycle. See the warning below.

Follow-ups

• Palindrome Linked List: the same first two steps, then compare the halves node by node instead of interleaving. Reverse the back half again afterwards to restore the input.
• Odd Even Linked List: move all nodes at odd positions before all nodes at even positions — two tails that each take every other node, then join. One pass, O(1).
• Undo the reorder: split the list by position (odd and even steps), reverse the second part, and append it. The same three kinds of step, in reverse.