Reorder List — Split, Reverse, Merge in One Pass

Problem Statement#

You are given the head of a singly linked list. The list can be represented as: L0 → L1 → … → Ln-1 → Ln. Reorder it to: L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → … You may not modify the values in the list's nodes. Only nodes themselves may be changed.

Constraints:

• The number of nodes in the list is in the range [1, 5 * 10^4]
• 1 <= Node.val <= 1000

Example 1:

Input:  head = [1, 2, 3, 4]
Output: [1, 4, 2, 3]

Example 2:

Input:  head = [1, 2, 3, 4, 5]
Output: [1, 5, 2, 4, 3]

Example 3:

Input:  head = [1]
Output: [1]

Why This Problem Matters#

Reorder List (LeetCode 143) is a composite problem — it requires you to combine three separate linked list techniques in sequence. Facebook, Amazon, and Google use it in interviews because it's impossible to solve elegantly without knowing all three patterns, and the composition reveals whether you understand how they interact.

The three techniques are:

1. Fast/slow pointer midpoint — identical to Palindrome Linked List (LC 234)
2. In-place reversal of second half — identical to Reverse Linked List (LC 206)
3. Interleaved merge of two lists — a variant of Merge Two Sorted Lists (LC 21) without the comparison

Candidates who know all three patterns individually but have never composed them often struggle here. The key is recognizing that each phase produces a clean input for the next phase.

This problem also appears in disguised forms: "given a sequence, rearrange it as first-last-second-second_to_last-..." in array problems, or "create a balanced BST from a sorted array by interleaving" conceptually uses the same alternating pick pattern.

The Core Insight#

The reordering pattern L0 → Ln → L1 → Ln-1 → ... is equivalent to: take one from the front of the first half, then one from the back of the second half (alternating). If you split the list at the midpoint and reverse the second half, you have two lists you can merge by alternation:

• First half: L0 → L1 → L2 → ...
• Second half reversed: Ln → Ln-1 → Ln-2 → ...

Then merge by taking one from each list alternately until the second list is exhausted.

Visual Dry Run#

Input: 1 -> 2 -> 3 -> 4 -> 5

Phase 1: Find midpoint with fast/slow

fast.next = None → stop. slow = node 3 (midpoint).

Phase 2: Reverse second half (starting from slow.next = 4)

Cut: slow.next = None → first half: 1 -> 2 -> 3

Reverse 4 -> 5: prev = None, apply 3-pointer reversal.

• curr=4: nxt=5, 4->None, prev=4, curr=5
• curr=5: nxt=None, 5->4, prev=5, curr=None
• Second half reversed: 5 -> 4

Phase 3: Interleaved merge

l1 = 1 -> 2 -> 3, l2 = 5 -> 4

l2 exhausted → stop. Result: 1 -> 5 -> 2 -> 4 -> 3

Solution (Optimal)#

Python#

def reorderList(head):
    if not head or not head.next:
        return
 
    # Phase 1: Find midpoint
    slow, fast = head, head
    while fast.next and fast.next.next:
        slow = slow.next
        fast = fast.next.next
 
    # Phase 2: Reverse the second half
    prev, curr = None, slow.next
    slow.next = None  # cut the list at midpoint
    while curr:
        nxt = curr.next
        curr.next = prev
        prev = curr
        curr = nxt
    # prev is now the head of the reversed second half
 
    # Phase 3: Interleaved merge
    l1, l2 = head, prev
    while l2:
        # Save next pointers before rewiring
        l1_next = l1.next
        l2_next = l2.next
        # Insert l2 node after l1 node
        l1.next = l2
        l2.next = l1_next
        # Advance both pointers
        l1 = l1_next
        l2 = l2_next

Note: This function modifies the list in place and returns nothing (the LeetCode signature is void).

Time complexity: O(n) — three linear passes.

Space complexity: O(1) — only pointer variables.

JavaScript#

var reorderList = function(head) {
    if (!head || !head.next) return;
 
    // Phase 1: Find midpoint
    let slow = head, fast = head;
    while (fast.next !== null && fast.next.next !== null) {
        slow = slow.next;
        fast = fast.next.next;
    }
 
    // Phase 2: Reverse second half
    let prev = null, curr = slow.next;
    slow.next = null;
    while (curr !== null) {
        const nxt = curr.next;
        curr.next = prev;
        prev = curr;
        curr = nxt;
    }
 
    // Phase 3: Interleaved merge
    let l1 = head, l2 = prev;
    while (l2 !== null) {
        const l1Next = l1.next;
        const l2Next = l2.next;
        l1.next = l2;
        l2.next = l1Next;
        l1 = l1Next;
        l2 = l2Next;
    }
};

Complexity:

Common Mistakes#

1. Wrong midpoint for even-length lists. For [1, 2, 3, 4], the midpoint should be node 2 (so first half is 1->2 and second half is 3->4). Use while fast.next and fast.next.next — this stops slow at the correct position. If you use while fast and fast.next, slow stops one position later, giving a wrong split.

2. Not cutting the list at slow.next = None. If you don't sever the first half from the second before reversing, the reversal operates on the full remaining list, and the merge step gets confused by the still-linked nodes.

3. Saving l1_next and l2_next after rewiring instead of before. In the merge phase, you must save l1_next = l1.next and l2_next = l2.next BEFORE you rewire l1.next = l2 and l2.next = l1_next. After the rewire, l1.next has changed and the original reference is lost.

4. Looping while l1 instead of while l2. The second half is shorter than or equal to the first half (for odd-length lists, the middle node is in the first half). Loop while l2 is non-null. When l2 is exhausted, the remaining first-half nodes are already in place.

5. Returning head from a void function. The LeetCode signature is void reorderList(ListNode head). The function modifies in place. Don't return — the change is reflected in the original head.

Interview Tips#

1. Identify the three phases upfront: "I'll split this into three steps: find the midpoint with fast/slow pointers, reverse the second half in place, then interleave-merge the two halves."

2. Draw the split and reversal: On the whiteboard, physically show the two sub-lists after Phase 1 and 2. This makes Phase 3 obvious.

3. Test with even and odd lengths: [1,2,3,4] → [1,4,2,3] and [1,2,3,4,5] → [1,5,2,4,3].

4. Emphasize the cut: "After finding the midpoint at slow, I cut the list by setting slow.next = None. Without this cut, the two halves are still connected and the merge gets confused."

5. Connect to building blocks: "Phase 1 is the same as Palindrome Linked List's midpoint step. Phase 2 is the same as Reverse Linked List. Phase 3 is a variant of Merge Two Lists without comparison."

Follow-up Questions#

Q: What if you need to do this in place without modifying the original structure? Not possible in O(1) extra space for a singly linked list — you'd need to copy the values to an array, compute the reordering, and write back. That's O(n) space.

Q: What if you could use a stack? Push all values to a stack (O(n) space). Pop from the stack for "back" elements and traverse forward for "front" elements. Simpler but O(n) space.

Q: How does the midpoint condition differ between this and Palindrome LL? Palindrome Linked List uses while fast and fast.next to find the midpoint. Reorder List uses while fast.next and fast.next.next. For even-length lists, these give different midpoints. Reorder List needs the left-midpoint so the two halves are equal or first half is longer by 1.

Q: What's the space complexity of using recursion? A recursive approach that reaches the end via the call stack and pairs with front nodes uses O(n) stack space. Not optimal for this problem.

Q: Can you do it bottom-up? Not naturally — the interleaving from front-to-back and back-to-front is inherently non-reversible without knowing the endpoints.

Key Takeaways#

• Reorder List = find midpoint (fast/slow) + reverse second half (3-pointer) + interleaved merge. Execute in that order.
• Cut the list at slow.next = None after finding the midpoint before reversing.
• In the merge phase, save l1_next and l2_next before rewiring — otherwise you lose forward references.
• Drive the merge loop with while l2 — the second half is shorter than or equal to the first.
• The function is void (in-place modification) — no return value.
• Time O(n), Space O(1) — three linear passes, pointer variables only.