Free lesson · DSA Mastery - Interview Prep, End to End

Sort List

Medium8 min readdsasorting-advanced-applications

Sort List

Sort List applies merge sort to a linked list - the data structure merge sort is uniquely well-suited to. Without random access you can't pick a middle index in O(1), and quicksort's partitioning is awkward, but merge sort adapts beautifully: find the middle with slow/fast pointers, recursively sort each half, and merge by relinking nodes rather than copying values. The payoff is O(n log n) time with O(1) auxiliary space (ignoring recursion) - no buffer needed, because you splice pointers instead of moving data. It's the cleanest demonstration that merge sort's logic is about order, not array indexing. We present the top-down recursive merge sort and a bottom-up O(1)-stack variant.

The insight: the merge step on a linked list is even more natural than on an array - you just rewire next pointers to thread the smaller node each time. Splitting is the only new wrinkle, solved with the slow/fast pointer technique you've used since the linked-list section.

The Problem

Given the head of a linked list, return the list after sorting it in ascending order.

Example 1:

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

Example 2:

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

Example 3:

Input:  head = []
Output: []

Constraints:

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

Follow-up: Can you sort the linked list in O(n log n) time and O(1) memory (i.e., constant space)?

Approaches Overview

Top-down splits with slow/fast pointers and recurses - clearest to write. Bottom-up merges runs of size 1, 2, 4, … iteratively, achieving true O(1) space by avoiding the recursion stack.

Approach 1: Top-Down Recursive Merge Sort - Cleanest

The Idea

If the list has 0 or 1 nodes it's sorted. Otherwise, use slow/fast pointers to find the middle and split the list into two halves (cut the next link before the second half). Recursively sort each half, then merge the two sorted lists by relinking nodes via a dummy head. The merge threads the smaller current node each step - pure pointer surgery, no value copying.

Logic Flowchart

graph TD
    A["sortList(head)"] --> B{"head null or head.next null?"}
    B -->|Yes| C["return head (base case)"]
    B -->|No| D["slow/fast find middle; split into left, right"]
    D --> E["left = sortList(left)"]
    E --> F["right = sortList(right)"]
    F --> G["merge(left, right) by relinking"]
    G --> H["return merged head"]

    style A fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style B fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style C fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style D fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style E fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style F fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style G fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style H fill:#16a34a,stroke:#10b981,color:#f1f5f9

This flowchart shows top-down list merge sort. We find the middle with slow and fast pointers, split the list, recursively sort each half, then merge the two sorted halves by relinking nodes. No values are copied; only pointers change.

Code

public static ListNode sortList(ListNode head) {
    if (head == null || head.next == null) return head;   // 0 or 1 node

    // split: slow ends at the node before the second half
    ListNode slow = head, fast = head.next;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    ListNode right = slow.next;
    slow.next = null;                                      // cut into two halves

    ListNode left = sortList(head);
    right = sortList(right);
    return merge(left, right);
}

private static ListNode merge(ListNode a, ListNode b) {
    ListNode dummy = new ListNode(0), tail = dummy;
    while (a != null && b != null) {
        if (a.val <= b.val) { tail.next = a; a = a.next; }
        else                { tail.next = b; b = b.next; }
        tail = tail.next;
    }
    tail.next = (a != null) ? a : b;                       // attach the remainder
    return dummy.next;
}

// ListNode: int val; ListNode next;
// Usage: sortList([4,2,1,3]) -> [1,2,3,4]

This Java code sorts a linked list top-down. Slow and fast pointers find the middle, the list is cut into two halves, each is recursively sorted, and the merge relinks nodes by threading the smaller value through a dummy head. Only pointers are rewired.

Step-by-Step Walkthrough

A frame-by-frame trace on head = [4,2,1,3]:

graph LR
    F0["split [4,2,1,3] → [4,2] [1,3]"]
    F1["[4,2] → [4] [2] merge → [2,4]"]
    F2["[1,3] → [1] [3] merge → [1,3]"]
    F3["merge [2,4] & [1,3]:<br/>relink 1,2,3,4"]
    F4["sorted [1,2,3,4]"]
    F0 --> F1 --> F2 --> F3 --> F4

    style F0 fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style F1 fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style F2 fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style F3 fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style F4 fill:#16a34a,stroke:#10b981,color:#f1f5f9

This walkthrough sorts four, two, one, three. It splits into four-two and one-three, sorts each into two-four and one-three, then merges by relinking into one, two, three, four.

Result: [1, 2, 3, 4].

Complexity

Time: O(n log n) - log n split levels, O(n) merge per level. Space: O(log n) - recursion stack (no data buffer).

Approach 2: Bottom-Up Merge Sort - Meets the Follow-Up

The Idea

Avoid recursion entirely. Let step grow as 1, 2, 4, …, up to n. In each pass, repeatedly take two consecutive sublists of length step, merge them, and stitch the merged runs back into one list. After log n passes the whole list is sorted. Splitting is done by walking step nodes and cutting; merging reuses the same relink routine. No recursion stack and no buffer → O(1) auxiliary space.

Logic Flowchart

graph TD
    A["n = length(head); dummy.next = head"] --> B["for step = 1; step < n; step *= 2"]
    B --> C["cur = dummy.next; tail = dummy"]
    C --> D["split off left (step nodes) and right (step nodes)"]
    D --> E["merge left, right; append to tail; advance tail"]
    E --> F{"more runs in this pass?"}
    F -->|Yes| D
    F -->|No| G{"step < n?"}
    G -->|Yes| B
    G -->|No| H["return dummy.next"]

    style A fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style B fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style C fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style D fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style E fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style F fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style G fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style H fill:#16a34a,stroke:#10b981,color:#f1f5f9

This flowchart shows bottom-up list merge sort. With run length doubling each pass, we repeatedly split off two runs, merge them, and append to a growing result. After log n passes the list is sorted, using no recursion stack and no buffer.

Code

public static ListNode sortListBottomUp(ListNode head) {
    int n = 0;
    for (ListNode c = head; c != null; c = c.next) n++;
    ListNode dummy = new ListNode(0);
    dummy.next = head;

    for (int step = 1; step < n; step *= 2) {
        ListNode cur = dummy.next, tail = dummy;
        while (cur != null) {
            ListNode left = cur;
            ListNode right = split(left, step);     // cut after `step` nodes
            cur = split(right, step);                // remainder for next iteration
            tail = mergeTail(left, right, tail);     // merge and attach; return new tail
        }
    }
    return dummy.next;
}

// cut list after `step` nodes; return head of the remainder
private static ListNode split(ListNode head, int step) {
    for (int i = 1; head != null && i < step; i++) head = head.next;
    if (head == null) return null;
    ListNode rest = head.next;
    head.next = null;
    return rest;
}

// merge a and b, append to tail, return the new tail
private static ListNode mergeTail(ListNode a, ListNode b, ListNode tail) {
    while (a != null && b != null) {
        if (a.val <= b.val) { tail.next = a; a = a.next; }
        else                { tail.next = b; b = b.next; }
        tail = tail.next;
    }
    tail.next = (a != null) ? a : b;
    while (tail.next != null) tail = tail.next;       // advance to the real end
    return tail;
}

This Java code sorts the list bottom-up. Run length doubles each pass; within a pass it splits off two runs of the current length, merges them, and appends to a growing result anchored at a dummy head. It uses constant auxiliary space.

Complexity

Time: O(n log n) - log n passes, O(n) work per pass. Space: O(1) - no recursion, no buffer. Meets the follow-up.

Complexity Comparison

Both are merge sort; the difference is recursion vs iteration. Top-down is the cleanest to write and reason about; bottom-up earns the coveted O(1) space by trading recursion for an explicit pass loop. Merge sort's pointer-relinking merge is what makes either possible without a value buffer.

Variations & Follow-ups

Why is merge sort better than quicksort for linked lists?

Merge sort needs only sequential access (find middle, walk, relink) - exactly what a linked list provides cheaply. Quicksort relies on partitioning around a pivot, which needs efficient random access and swaps; on a list, partitioning is clumsy and the pivot-driven worst case still looms. Merge sort's linear merge maps perfectly onto pointer rewiring.

Why does the list merge need no extra buffer?

On an array, merging writes into a separate buffer because you can't reorder in place without overwriting. On a list, you reorder by changing next pointers - the nodes themselves never move, so no buffer is required. This is why list merge sort hits O(1) auxiliary space (bottom-up) where array merge sort needs O(n).

Why fast = head.next when finding the middle?

Starting fast one ahead biases slow to stop at the end of the first half for even-length lists, so the split yields two halves of nearly equal size and the cut (slow.next = null) lands correctly. Starting fast = head can place slow one node too far and complicate the split.

What about edge cases?

• Empty or single node (Example 3): Returned immediately by the base case.
• Already sorted: Still O(n log n); merges are trivial but all passes run.
• Duplicates: <= in the merge keeps them stably ordered.
• Negative values (Example 2): Compared directly; no special handling.

Common Interview Pitfalls

• Forgetting to cut the list (slow.next = null). Without the cut, the two halves still share nodes and the recursion never terminates.
• Infinite loop in the split. Ensure fast = head.next (or handle the two-node case) so slow advances correctly.
• Losing the remainder in bottom-up. Capture cur for the next pair before merging, since merging rewires next.
• Not advancing tail to the true end after attaching the remainder. The next merge must append after the last node.

Why This Problem Matters

Sort List proves that merge sort is fundamentally about order, not indexing - it adapts to a pointer-based structure with less memory than the array version. The slow/fast split and relink-merge are reusable list techniques, and the bottom-up variant is a favorite follow-up because it forces a genuinely iterative, constant-space implementation.

The next topic, Reverse Pairs, is where merge sort becomes a counting tool: count pairs (i, j) with i < j and nums[i] > 2 * nums[j]. The trick is to count these cross-pairs during the merge, when both halves are sorted - a batch count in O(1) per right element - so the total counting rides along on the O(n log n) sort. This is the first true "merge sort counts something" problem.

Back to DSA Mastery - Interview Prep, End to End