Sort List

MediumLinked List · Merge Sort🧩 Recursion & Divide and Conquer LeetCode #148 ↗Updated Oct 30, 2026

Problem

Given the head of a singly linked list, rearrange it so the values are in ascending order and return the new head. Aim for O(n log n) time; ideally relink the existing nodes rather than creating new ones.

Input[4,2,1,3]Output[1,2,3,4]

Input[-1,5,3,4,0]Output[-1,0,3,4,5]

Input[]Output[]

0 ≤ n ≤ 5·10⁴ · -10⁵ ≤ Node.val ≤ 10⁵ · Follow-up: O(n log n) time and O(1) extra space.

Try it yourself

Java

class Solution {
    public ListNode sortList(ListNode head) {
        
    }
}

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

Merge sort fits linked lists perfectly: merging two sorted lists needs only pointer rewiring (no buffer), and splitting is cheap. Doing it bottom-up (runs of 1, 2, 4, …) removes the recursion stack and meets the O(1)-space follow-up.

PatternRecursion & Divide and Conquer

Instinct If the answer for n items can be built from the same problem on halves (or smaller pieces) plus a cheap combine step - split, recurse, merge.

Memory hack Split it, trust it, stitch it - nail the base case, take the leap of faith on smaller calls, then glue their answers together.

Open the Recursion & Divide and Conquer guide →

Approaches

Brute ForceCopy Values, Sort Array, Write Back

Time O(n log n)Space O(n)

Dump all values into an array, sort it with the library, then walk the list again and overwrite each node's val in order. The node structure never changes, only the values.

Java

public ListNode sortList(ListNode head) {
    List<Integer> vals = new ArrayList<>();
    for (ListNode p = head; p != null; p = p.next) vals.add(p.val);
    Collections.sort(vals);
    int i = 0;
    for (ListNode p = head; p != null; p = p.next) p.val = vals.get(i++);
    return head;
}

Fast in practice, but O(n) extra memory and it rewrites values instead of relinking.

BetterTop-Down Merge Sort

Time O(n log n)Space O(log n)

Find the middle with slow/fast pointers, cut the list there, sort both halves recursively and merge them with a dummy head. log n levels × O(n) merging per level; the only extra memory is the recursion stack.

Java

public ListNode sortList(ListNode head) {
    if (head == null || head.next == null) return head;
    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
    return merge(sortList(head), sortList(right));
}
private ListNode merge(ListNode a, ListNode b) {
    ListNode dummy = new ListNode(0), t = dummy;
    while (a != null && b != null) {
        if (a.val <= b.val) { t.next = a; a = a.next; }
        else { t.next = b; b = b.next; }
        t = t.next;
    }
    t.next = (a != null) ? a : b;
    return dummy.next;
}

The standard answer; uses O(log n) stack, so it misses the strict O(1) follow-up.

OptimalBottom-Up Merge Sort (Iterative)

Time O(n log n)Space O(1)

Treat every node as a sorted run of size 1. In each pass, walk the list, cut off two runs of size step, merge them and attach the result after tail. Double step until it reaches n. No recursion ⇒ constant extra space.

Java

public ListNode sortList(ListNode head) {
    int n = 0;
    for (ListNode p = head; p != null; p = p.next) n++;
    ListNode dummy = new ListNode(0, head);
    for (int step = 1; step < n; step *= 2) {
        ListNode tail = dummy, cur = dummy.next;
        while (cur != null) {
            ListNode left = cur;
            ListNode right = split(left, step);
            cur = split(right, step);
            tail = merge(left, right, tail);
        }
    }
    return dummy.next;
}
private 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;
}
private ListNode merge(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;
    return tail;
}

Dry run[4,2,1,3]

L left runR right run changed

step=1
2
L
4
R
1

3

merge [4]+[2]
step=1
2

4

1
L
3
R
merge [1]+[3]
step=2
1
L
2

3
R
4

merge [2,4]+[1,3] ✔

Same O(n log n), but truly O(1) extra space — answers the follow-up.

At a glance

Level	Approach	Time	Space
Brute Force	Copy Values, Sort Array, Write Back	`O(n log n)`	`O(n)`
Better	Top-Down Merge Sort	`O(n log n)`	`O(log n)`
Optimal	Bottom-Up Merge Sort (Iterative)	`O(n log n)`	`O(1)`

Common pitfalls

Not cutting slow.next = null — the halves overlap and recursion never ends.
Bottom-up: losing the remainder — save cur = split(right, step) before merging.
Using < instead of <= in merge loses stability (harmless here, but say so).

Interview tips

Explain why merge sort (not quicksort) suits lists: no random access, merge is O(1) space.
Point out recursion depth is O(log n), so top-down is not strictly O(1) space.
Reuse “Merge Two Sorted Lists” and “Middle of the Linked List” as building blocks.

Pattern

Merge sort on linked lists → sort or merge lists in O(n log n) with only pointer rewiring.

My notes saved in this browser