Rearrange a LinkedList (Reorder List)

• Reorder List rearranges a linked list so nodes interleave from the front and back: first, last, second, second-to-last, and so on.
• Three steps: find the middle with fast-slow pointers, reverse the second half in place, then merge the two halves by alternating nodes.
• In-place means no new nodes are allocated; only existing next pointers are rewired.
• Cycle prevention requires breaking the link between the first half's tail and the second half before merging.
• Complexity is O(n) time and O(1) space.

What is the Reorder List problem?

Given a singly linked list L0 -> L1 -> L2 -> ... -> Ln, reorder it to L0 -> Ln -> L1 -> Ln-1 -> L2 -> Ln-2 -> .... The nodes must interleave from the front and back of the original list. You must do this in place without allocating new nodes.

For example, 1 -> 2 -> 3 -> 4 becomes 1 -> 4 -> 2 -> 3. For 1 -> 2 -> 3 -> 4 -> 5, the result is 1 -> 5 -> 2 -> 4 -> 3.

package com.bank.service;

public class StatementNode {
    int pageNumber;
    StatementNode next;

    public StatementNode(int pageNumber) {
        this.pageNumber = pageNumber;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        StatementNode current = this;
        while (current != null) {
            sb.append(current.pageNumber);
            if (current.next != null) sb.append(" -> ");
            current = current.next;
        }
        return sb.toString();
    }
}

Why does this problem exist?

This problem tests whether you can compose multiple fundamental linked list operations into a single solution. It requires three skills: finding the middle, reversing a list, and merging two lists. Each skill is simple on its own, but combining them correctly, especially avoiding cycles, is what makes this an intermediate-to-hard problem.

In banking, this pattern appears when reordering statement pages for side-by-side comparison: the reviewer wants to see the first and last pages adjacent for cross-referencing opening and closing balances.

// Banking use case: interleave statement pages for review
// Original: Page1 -> Page2 -> Page3 -> Page4 -> Page5 -> Page6
// Reordered: Page1 -> Page6 -> Page2 -> Page5 -> Page3 -> Page4
// Reviewer sees opening and closing pages side by side

How does the three-step algorithm work?

The algorithm has three phases:

Phase 1: Find the middle using fast-slow pointers. Slow moves one node, fast moves two. When fast reaches the end, slow is at the midpoint. Save the node after slow as the head of the second half, then break the link by setting slow.next = null.

Phase 2: Reverse the second half using the standard three-pointer reversal (prev, curr, next). After reversal, the second half runs backward from the original tail to the original midpoint.

Phase 3: Merge the two halves by alternating. Take one node from the first half, then one from the reversed second half, relinking next pointers.

package com.bank.service;

public class StatementReorder {

    public static void reorder(StatementNode head) {
        if (head == null || head.next == null) return;

        // Phase 1: find the middle
        StatementNode slow = head, fast = head;
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        StatementNode secondHalf = slow.next;
        slow.next = null; // break the link to prevent cycles

        // Phase 2: reverse the second half
        secondHalf = reverse(secondHalf);

        // Phase 3: merge alternately
        merge(head, secondHalf);
    }

    private static StatementNode reverse(StatementNode head) {
        StatementNode prev = null;
        StatementNode curr = head;
        while (curr != null) {
            StatementNode next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }

    private static void merge(StatementNode first, StatementNode second) {
        while (second != null) {
            StatementNode firstNext = first.next;
            StatementNode secondNext = second.next;
            first.next = second;
            second.next = firstNext;
            first = firstNext;
            second = secondNext;
        }
    }

    public static void main(String[] args) {
        StatementNode n1 = new StatementNode(1);
        StatementNode n2 = new StatementNode(2);
        StatementNode n3 = new StatementNode(3);
        StatementNode n4 = new StatementNode(4);
        n1.next = n2; n2.next = n3; n3.next = n4;

        System.out.println("Before: " + n1);
        reorder(n1);
        System.out.println("After:  " + n1);
    }
}

Before: 1 -> 2 -> 3 -> 4
After:  1 -> 4 -> 2 -> 3

How does each phase work in detail?

The middle-finding phase uses the first-middle variant (fast.next != null && fast.next.next != null) so that for even-length lists, slow lands on the last node of the first half. This makes it easy to break the link cleanly.

The reversal phase uses the standard three-pointer technique. The prev pointer starts as null, and for each node, we save next, point curr.next back to prev, then advance both prev and curr. After the loop, prev is the new head of the reversed second half.

The merge phase takes one node from each half alternately. It saves the next pointers of both current nodes, then rewires: first.next = second and second.next = firstNext. Then it advances both pointers. The loop continues until the second half is exhausted.

// Trace for [1, 2, 3, 4, 5]
// Phase 1: slow=2, fast=5. secondHalf = 3 -> 4 -> 5. Break: 2.next = null
//   First half: 1 -> 2
//   Second half: 3 -> 4 -> 5
// Phase 2: reverse second half: 5 -> 4 -> 3
// Phase 3: merge
//   Step 1: first=1, second=5 -> 1 -> 5 -> 2, advance first=2, second=4
//   Step 2: first=2, second=4 -> 2 -> 4 -> null, advance first=null, second=3
//   Step 3: first=null but second=3. Wait - first half ended.
//   Actually: after step 2, first=null so second.next handles the tail.
// Result: 1 -> 5 -> 2 -> 4 -> 3

How is this different from the naive array approach?

The naive approach stores all nodes in an array for random access, then rewires pointers by picking from the front and back alternately. This uses O(n) extra space.

| Aspect | Array approach | Three-step in-place |
|---|---|---|
| Extra space | O(n) for the array | O(1) pointer variables |
| Time | O(n) | O(n) |
| Complexity | Simpler to code | Three techniques combined |
| Interview preference | Acceptable but not impressive | Expected answer |

// Naive array approach: O(n) extra space
public static void reorderNaive(StatementNode head) {
    java.util.List<StatementNode> nodes = new java.util.ArrayList<>();
    StatementNode current = head;
    while (current != null) {
        nodes.add(current);
        current = current.next;
    }
    int left = 0, right = nodes.size() - 1;
    while (left < right) {
        nodes.get(left).next = nodes.get(right);
        left++;
        if (left == right) break;
        nodes.get(right).next = nodes.get(left);
        right--;
    }
    nodes.get(left).next = null;
}

What are the edge cases?

The edge cases to handle are:

- **Empty list or single node**: nothing to reorder, return immediately.
- **Two nodes**: `1 -> 2` stays as `1 -> 2`. The second half is just node 2, reversed is still node 2, merged is `1 -> 2`.
- **Three nodes**: `1 -> 2 -> 3` becomes `1 -> 3 -> 2`. The first half is `1 -> 2`, second half is `3`, reversed is `3`, merged gives `1 -> 3 -> 2`.
- **Odd length**: the first half has one more node than the second half. The extra node naturally terminates the merged chain.

public class ReorderEdgeCases {
    public static void main(String[] args) {
        // Two nodes
        StatementNode a = new StatementNode(1);
        StatementNode b = new StatementNode(2);
        a.next = b;
        StatementReorder.reorder(a);
        System.out.println("Two: " + a);

        // Three nodes
        StatementNode x = new StatementNode(1);
        StatementNode y = new StatementNode(2);
        StatementNode z = new StatementNode(3);
        x.next = y; y.next = z;
        StatementReorder.reorder(x);
        System.out.println("Three: " + x);
    }
}

Two: 1 -> 2
Three: 1 -> 3 -> 2

What are common mistakes?

The most dangerous mistake is forgetting to break the link between the first half and the second half. Without slow.next = null, the merge can wire the chain back into itself and create a cycle that causes infinite loops in any downstream traversal.

// WRONG: does not break the link
StatementNode secondHalf = slow.next;
// Missing: slow.next = null;
secondHalf = reverse(secondHalf);
merge(head, secondHalf);
// The first half still points into the reversed second half,
// creating a cycle: 1 -> 2 -> ... -> 4 -> 3 -> 2 -> ... (infinite loop)

// CORRECT: break the link before reversing and merging
StatementNode secondHalf = slow.next;
slow.next = null; // clean cut prevents cycles
secondHalf = reverse(secondHalf);
merge(head, secondHalf);

Another common mistake is using the wrong loop condition for finding the middle, which splits the list at the wrong point and produces incorrect reordering for even-length lists.

What is the time and space complexity?

Each of the three phases runs in O(n) time: finding the middle is one pass, reversal is one pass over the second half, and merging is one pass interleaving both halves. The total time is O(n).

The space is O(1) because only a constant number of pointer variables are used. No new nodes are allocated; only existing next pointers are rewired.

// Phase 1: O(n/2) to find middle
// Phase 2: O(n/2) to reverse second half
// Phase 3: O(n/2) to merge
// Total: O(n) time, O(1) space

What should a senior engineer know?

A senior engineer should know that this problem is a direct composition of three building blocks, and mastering those blocks separately makes this problem straightforward. The cycle hazard is the production-critical detail: in a real system, a cycle in a linked list causes infinite loops, memory leaks, or stack overflows in any code that traverses the list.

The same three-step pattern (split, reverse, merge) appears in other problems: sorting a linked list (merge sort), checking if a list is a palindrome, and folding a list. Recognizing the pattern saves time in interviews.

What are common interview follow-up questions?

Interviewers often ask:

• Can you do this without reversing the second half? Yes, using a stack or deque, but that uses O(n) space.
• What if you need to return a new list instead of modifying in place? Clone nodes during the merge step.
• How would you verify the result is correct? Traverse the reordered list and check that the sequence matches the expected interleaving.
• What is the connection to the palindrome check? The palindrome check uses the same first two steps (find middle, reverse second half) but then compares instead of merging.