Foundation · Module 10 · Lesson 5

Merge & reorder

Split, interleave, merge, and partition lists.

15–25 min readLesson 57 of 123

Lesson 57 of 123

1d streak

In-Place Splicing: Merging Sorted Lists in O(1) Auxiliary Space

Merging two sorted linked lists into one contiguous sorted list demonstrates the supreme advantage of pointer structures over arrays: in-place splicing. Rather than allocating new node wrappers, we rewire the existing next pointers of the input nodes. A sentinel dummy head tracks the merged origin, and a trailing tail pointer splices the next smallest node.

Architectural Boundary · Do Not Confuse

Concept A

Array Merge (Merge Sort): O(n + m) Memory

Concept B

Linked List Merge: O(1) Memory

Merging sorted arrays requires an external buffer array of size n + m to prevent overwriting unread elements during element transfers. Linked lists splice existing heap nodes via reference redirection, consuming strictly zero additional heap memory.

The O(1) Remainder Splice

In an array merge, when one array runs out of elements, the remaining suffix of the other array must be copied element-by-element in O(k) steps. In a linked list merge, when one list reaches null, the entire remaining chain is attached in a single O(1) pointer assignment: tail.next = (l1 != null) ? l1 : l2;.

MergeTwoLists.javajava

// In-Place Sorted List Splice: O(n + m) Time, O(1) Auxiliary Space
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
    ListNode dummy = new ListNode(-1);
    ListNode tail = dummy;

    while (list1 != null && list2 != null) {
        if (list1.val <= list2.val) {
            tail.next = list1;
            list1 = list1.next;
        } else {
            tail.next = list2;
            list2 = list2.next;
        }
        tail = tail.next;
    }

    // O(1) instant splice of remaining suffix
    tail.next = (list1 != null) ? list1 : list2;

    return dummy.next;
}

Active Recall Checkpoint

Why does tail.next = (list1 != null) ? list1 : l2; take O(1) time instead of O(k)?

Show answer & explanation

Because list1 and list2 are already internally linked chains. Assigning the reference connects the tail directly to the head of the remaining chain without traversing its nodes.

Merge Sort on Linked Lists: O(n log n) Without Auxiliary Arrays

Merge Sort is universally recognized as the optimal sorting algorithm for linked lists. On contiguous arrays, Quicksort is typically preferred over Merge Sort due to superior cache locality and in-place partitioning without an O(n) scratch array. On linked lists, the exact reverse is true: Quicksort suffers because finding a partition pivot requires O(n) pointer stepping and exhibits terrible cache thrashing, whereas Merge Sort operates in guaranteed O(n log n) time with O(1) auxiliary heap space.

Algorithm	Array Performance	Linked List Performance	Primary Limiting Factor on Lists
Merge Sort	O(n log n) time, O(n) space	O(n log n) time, O(1) aux space	Optimal: sequential traversal matches list design
Quicksort	O(n log n) avg, O(1) space	O(n²) worst-case, poor locality	No random access to pivot index, unstable partition
Heapsort	O(n log n) time, O(1) space	Extremely inefficient O(n log n)	Parent/child 2i + 1 index arithmetic impossible

01Base Case: If head == null or head.next == null, return head (already sorted).
02Find Left Midpoint: Advance fast/slow pointers with while (fast.next != null && fast.next.next != null).
03Sever the Chain: ListNode mid = slow.next; slow.next = null; bisects the list into two disconnected sublists.
04Recurse: Sort both halves: ListNode left = sortList(head); ListNode right = sortList(mid);.
05Merge: Combine sorted halves using mergeTwoLists(left, right).

SortList.javajava

public ListNode sortList(ListNode head) {
    if (head == null || head.next == null) return head;

    // 1. Bisect list using left-biased middle
    ListNode slow = head;
    ListNode fast = head;
    while (fast.next != null && fast.next.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }

    ListNode rightHead = slow.next;
    slow.next = null; // Sever link to create two independent lists

    // 2. Divide
    ListNode leftSorted = sortList(head);
    ListNode rightSorted = sortList(rightHead);

    // 3. Conquer via in-place merge
    return mergeTwoLists(leftSorted, rightSorted);
}

The Infinite Recursion Sever Trap

Failing to execute slow.next = null; before recursing is a fatal bug. Without severing the link, the left list still flows directly into the right list, causing the recursive call on the left half to re-process the entire original list, resulting in an immediate stack overflow.

Compound List Patterns: Palindrome Verification & Interleaving

Advanced linked list interview questions frequently synthesize three atomic operations into a single cohesive pipeline: (1) Find Midpoint via Fast/Slow pointers, (2) In-Place Suffix Reversal, and (3) Two-Pointer Interleaving or Node Comparison. This pipeline solves LeetCode 234 (Palindrome Linked List) and LeetCode 143 (Reorder List) in strictly O(n) time and O(1) auxiliary space.

01Phase 1: Find left-biased middle node (slow) using fast & slow pointers.
02Phase 2: Sever the first half from the second half (ListNode secondHalf = slow.next; slow.next = null;).
03Phase 3: Reverse the second half in-place (ListNode reversedHead = reverseList(secondHalf);).
04Phase 4 (Reorder): Interleave nodes by taking one from first half, then one from reversed second half.
05Phase 4 (Palindrome): Step through both halves simultaneously comparing values; return false on any mismatch.

ReorderList.javajava

// LeetCode 143: Reorder List (L0 -> Ln -> L1 -> Ln-1 -> ...)
public void reorderList(ListNode head) {
    if (head == null || head.next == null) return;

    // 1. Find midpoint (left-biased)
    ListNode slow = head, fast = head;
    while (fast.next != null && fast.next.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }

    // 2. Split and reverse second half
    ListNode secondHalf = slow.next;
    slow.next = null;
    ListNode p2 = reverse(secondHalf);
    ListNode p1 = head;

    // 3. Interleave two lists
    while (p2 != null) {
        ListNode tmp1 = p1.next;
        ListNode tmp2 = p2.next;

        p1.next = p2;
        p2.next = tmp1;

        p1 = tmp1;
        p2 = tmp2;
    }
}

private ListNode reverse(ListNode head) {
    ListNode prev = null, curr = head;
    while (curr != null) {
        ListNode nxt = curr.next;
        curr.next = prev;
        prev = curr;
        curr = nxt;
    }
    return prev;
}

Active Recall Checkpoint

In production systems, why should a Palindrome verification algorithm reverse the second half back to its original configuration before returning?

Show answer & explanation

To maintain structural immutability and prevent side-effect bugs. If other concurrent threads or downstream consumers hold references to the list, mutating it in-place during a read-only query creates subtle data corruption unless restored.

Use it when

Use the Split-Reverse-Merge/Interleave pipeline when solving complex linked list restructuring problems with strict O(1) space bounds.

Reconsider when

Reconsider if the list is shared across threads or if allocating an O(n) array of node references is acceptable for simpler, less error-prone code.

Cost Model

Complexity & Trade-offs

OperationTimeSpaceWhy

Split, reverse, merge

O(n)

O(1)

The bound follows from the number of states visited and the work performed per transition.

When to use it

Frequent local insertions, deletions, chain rewiring, and cycle analysis.
Problems where contiguous storage or random access is unnecessary.
In-place sequence transformations.

Common mistakes

Losing the unread suffix by overwriting next too early.
Failing to update head or tail after a boundary mutation.
Dereferencing null or looping forever on a cycle.

Practice prompts

Reproduce the worked Merge & reorder example without looking at the trace.
Change one input condition and explain whether the Merge & reorder invariant still holds.
Implement the approach, derive its cost, and compare it with a straightforward baseline.

Mastery check

Can you derive it instead of memorizing it?

State the invariant before looking at code.

Explain why every transition is safe.

Construct a worst-case input.

Name one alternative and its trade-off.