Reorder List: Three Classic Patterns in One Problem

Reorder List is LeetCode 143. It asks you to take a linked list and rearrange it by alternating nodes from the front and back. The first node, then the last node, then the second node, then the second-to-last node, and so on.

On the surface it sounds simple. But linked lists do not give you random access. You cannot just index into the back of the list. You are stuck going forward, one node at a time.

The trick is that this is not one problem. It is three problems glued together, and you have already seen each one before.

The problem

Given the head of a singly linked list, reorder it in place:

L0 -> L1 -> L2 -> ... -> Ln becomes L0 -> Ln -> L1 -> Ln-1 -> L2 -> Ln-2 -> ...

You cannot just change the values. You need to actually move the nodes.

Why this problem is a perfect test

Interviewers love reorder list LeetCode because it tests three skills at once. You need to:

1. Find the middle of the list (fast-slow pointer)
2. Reverse the second half (in-place linked list reversal)
3. Merge two lists by interleaving them (node-by-node rebuild)

If you know all three techniques cold, this problem takes five minutes. If you are missing even one, you will be stuck. That is what makes it such a good filter. It does not test cleverness. It tests whether you have actually drilled the fundamentals.

Phase 1: Find the middle

This is the classic tortoise-and-hare setup. Use a slow pointer that moves one step at a time and a fast pointer that moves two steps. When fast reaches the end, slow sits at the midpoint.

For a 5-node list 1 -> 2 -> 3 -> 4 -> 5, slow ends up at node 3. Everything after slow (nodes 4 and 5) is the second half.

This is the same technique you use in Palindrome Linked List, Linked List Cycle (Floyd's algorithm), and Middle of the Linked List (LeetCode 876). One brick, many problems.

Phase 2: Reverse the second half

Starting from slow.next, reverse the remaining nodes in place. This is the exact three-pointer technique from Reverse Linked List: save next, flip the arrow, advance prev and curr.

After reversing, the second half runs backwards. For our example, 4 -> 5 becomes 5 -> 4. Now the last node of the original list is the first node of the reversed half, which is exactly what we need for the interleave step.

We also cut the link between the first half and the second half. slow.next = None makes the first half end at the midpoint.

Phase 3: Interleave merge

Now you have two separate lists:

• First half: 1 -> 2 -> 3
• Reversed second half: 5 -> 4

Walk both lists simultaneously. At each step, take one node from the first list, then one node from the second list. Stitch them together by saving and rewiring next pointers.

This is the linked list reorder step that ties it all together. It is similar to the merge step in Merge Two Sorted Lists (LeetCode 21), but instead of comparing values, you just alternate: one from first, one from second, repeat.

Visual walkthrough

Let's trace through reordering 1 -> 2 -> 3 -> 4 -> 5. Watch the three phases play out step by step.

The result is 1 -> 5 -> 2 -> 4 -> 3. First, last, second, second-to-last, middle.

The solution

def reorderList(head):
    if not head or not head.next:
        return

    # Phase 1: find the middle
    slow = head
    fast = head
    while fast.next and fast.next.next:
        slow = slow.next
        fast = fast.next.next

    # Phase 2: reverse the second half
    prev = None
    curr = slow.next
    slow.next = None  # cut the first half from the second
    while curr:
        next_node = curr.next
        curr.next = prev
        prev = curr
        curr = next_node

    # Phase 3: interleave merge
    first = head
    second = prev  # head of the reversed second half
    while second:
        tmp1 = first.next
        tmp2 = second.next
        first.next = second
        second.next = tmp1
        first = tmp1
        second = tmp2

Three phases, three loops. Each one does a single job. No recursion, no extra data structures, no tricks.

Complexity analysis

Time: O(n). Each phase does a single pass through part of the list. Finding the middle is O(n/2), reversing is O(n/2), merging is O(n/2). That adds up to O(n) total.

Space: O(1). We only use a handful of pointer variables. No arrays, no hash maps, no stacks. Everything happens in place.

Edge cases

• Empty list or single node. Nothing to reorder. The early return handles this.
• Two nodes like 1 -> 2. slow stays at 1. We reverse the second half (just node 2). Then merge: 1 points to 2. No change needed, and the code handles it correctly.
• Even-length list like 1 -> 2 -> 3 -> 4. slow lands at 2. Second half is 3 -> 4, which reverses to 4 -> 3. Merge produces 1 -> 4 -> 2 -> 3. Correct.
• Odd-length list like 1 -> 2 -> 3 -> 4 -> 5. slow lands at 3. The first half has one more node than the second half. The merge loop ends when second is exhausted, and the extra node from first is already in the right place.

The Building Blocks

This problem is built from three core building blocks:

Fast-slow pointer. Two pointers moving at different speeds to find structural information about the list. The fast pointer reaches the end in n/2 steps, which means the slow pointer is sitting at the midpoint. This is the same technique from Palindrome Linked List and Linked List Cycle. It works because the 2:1 speed ratio guarantees the slow pointer covers exactly half the distance.

In-place linked list reversal. The three-pointer dance: save next, flip the arrow, advance. This is the core technique from Reverse Linked List (LeetCode 206). Here you apply it to just the second half, but the mechanics are identical. The reversed half gives you access to the last nodes first, which is exactly what you need for the interleave.

Node-by-node rebuild. Walking two lists simultaneously and stitching them together into a new arrangement. At each step you save both "next" pointers before rewiring, then advance. This is the same save-before-you-overwrite principle from reversal, applied to a merge context. It shows up in Merge Two Sorted Lists and anywhere you need to interleave or zip two linked lists.

These three bricks snap together naturally. Fast-slow gives you the split point. Reversal gives you access to the back of the list. Node-by-node rebuild weaves them together. Each piece is simple on its own. The challenge is combining them without mixing up your pointers.

Common mistakes

The most frequent bugs on this problem:

1. Wrong loop condition for finding the middle. Using while fast and fast.next instead of while fast.next and fast.next.next puts slow one node too far into the second half. The merge then produces the wrong result.
2. Forgetting to cut the link. If you skip slow.next = None, the first half still points into the (now reversed) second half. The merge loop can go in circles or produce extra nodes.
3. Losing pointers during the merge. If you do first.next = second before saving first.next, you just lost the rest of the first half. Always save before you rewire.

Why you will forget this (and how to fix it)

This problem has three phases and six pointer variables across them. That is a lot of state. The most common failure mode is not forgetting the idea. You will remember "find middle, reverse, merge." The failure mode is getting the pointer assignments wrong under pressure.

The fix is not reading the solution one more time. It is typing it from scratch, from memory, multiple times. The first time you will probably stall in the merge phase. The second time it goes smoother. By the fourth or fifth rep, your hands just know the three-loop structure. That is the point where this problem stops being hard.

Related posts

• Reverse Linked List - The core reversal technique used in phase 2
• Palindrome Linked List - Uses the same fast-slow plus reversal combo, with a comparison phase instead of a merge