Reorder List — InterviewPrepKit

Solving tips

Recognize the target as the first half interleaved with the reversed second half, and solve it by composing three classic routines.
Chain: (1) find the middle with slow/fast pointers, (2) reverse the second half in place, (3) merge the two halves alternately.
Set slow.next = None to cut the list before reversing, or the merge will loop forever or duplicate nodes.
Target O(n) time and O(1) space; relink nodes rather than rewriting values, and prefer iteration over recursion at 5e4 nodes.

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

Hint 1

The output alternates between two sequences: the first half in order, and the second half in reverse. Can you produce those two sequences?

Hint 2

With all nodes in an array, two indices (one at each end, moving inward) can relink everything. That costs O(n) space — what linked-list tools give you "second half, reversed" without an array?

Hint 3

Three classics chained together: (1) slow/fast pointers to find the middle, (2) reverse the second half in place, (3) merge the two halves alternately. Each step is a well-known routine; the problem is just their composition.

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

class Solution:
    def reorderList(self, 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). It passes the time limit — the constraint it violates is the follow-up’s O(1) space, and it’s the answer an interviewer will immediately ask you to improve.

Approach 2 — Middle + reverse + merge (optimal)

Insight: the target order is exactly first half interleaved with reversed second half. Each ingredient is a standard routine: the slow/fast (tortoise-and-hare) middle finder (fast advances two nodes per slow’s one, so slow stops midway), the in-place reversal (iteratively flip each next pointer), and an alternating splice of two lists. Composing them solves the problem with three O(n) sweeps and no storage.

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

class Solution:
    def reorderList(self, 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]:

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

first	second	list so far
1	5	1→5→2→3
2	4	1→5→2→4→3

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 handful 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

Insight: the well-known alternative frames it as: reorder the sublist strictly inside head and the tail, then splice head → tail → (reordered inner part). Finding the tail each time costs O(n), giving O(n²) unless you pass lengths cleverly; the commonly taught recursive variant 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

class Solution:
    def reorderList(self, head: Optional[ListNode]) -> None:
        self.front = head
        self.stop = False

        def visit(node: Optional[ListNode]) -> None:
            if not node:
                return
            visit(node.next)          # unwind from the tail backward
            if self.stop:
                return
            if self.front is node or self.front.next is node:
                node.next = None      # middle reached: terminate list
                self.stop = True
                return
            nxt = self.front.next     # weave: front -> node -> old front.next
            self.front.next = node
            node.next = nxt
            self.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 — elegant, but 5·10^4 frames will overflow Python’s default recursion limit, so the iterative Approach 2 is the safe 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 is the capstone of the linked-list trio: middle-finding, in-place reversal, and merging. None of the three is invented here — the skill is recognizing a scary-looking permutation as a composition of routines you already own. When a target order mixes “forward from the front” with “backward from the back”, think: split at the middle, reverse one side, merge.