#148 Sort List

Mediumsolve on LeetCode ↗

frequently reported atByteDance / TikTok Amazon Microsoft Meta

the problem

In plain words

Sort a singly linked list in ascending order. Follow-up: O(n log n) time and O(1) extra memory.

in head = [4,2,1,3]

out [1,2,3,4]

in head = [-1,5,3,4,0]

out [-1,0,3,4,5]

in head = []

out []

0 ≤ n ≤ 5·10⁴
-10⁵ ≤ Node.val ≤ 10⁵

your turn

Try it before you peek

Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.

Solve it in the browser

LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.

Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.

Marking the problem solved, or opening every hint, also shows it.

the aha

Key insight

patternMerge sort & merging sorted runs Fast & slow pointers

Lists have no random access, which kills quicksort's and heap sort's advantages — but merging two sorted lists is O(1) space by relinking. Merge sort is the natural fit.

solutions

From brute force to optimal

Let the library do the work, then overwrite node values.

Collect values.
Collections.sort.
Rewrite node values in order.

timeO(n log n)

The library sort.

spaceO(n)

The copied values.

javajava.util.*

1class Solution {2    public ListNode sortList(ListNode head) {3        List<Integer> values = new ArrayList<>();4        for (ListNode p = head; p != null; p = p.next) values.add(p.val);5        Collections.sort(values);6        int i = 0;7        for (ListNode p = head; p != null; p = p.next) p.val = values.get(i++); // rewrite in place8        return head;9    }10}

Find the middle with slow/fast pointers, cut, sort both halves, merge.

Base: 0 or 1 node.
slow/fast to find the middle; cut after slow.
Recurse on both halves.
Merge with a dummy head.

timeO(n log n)

log n levels, O(n) splitting + merging per level.

spaceO(log n)

Recursion stack only — no arrays.

javajava.util.*

1class Solution {2    public ListNode sortList(ListNode head) {3        if (head == null || head.next == null) return head;4        // Split in the middle with slow/fast pointers.5        ListNode slow = head, fast = head.next;6        while (fast != null && fast.next != null) {7            slow = slow.next;8            fast = fast.next.next;9        }10        ListNode right = slow.next;11        slow.next = null;                       // cut the list in two12        return merge(sortList(head), sortList(right));13    }14 15    private ListNode merge(ListNode a, ListNode b) {16        ListNode dummy = new ListNode(0), tail = dummy;17        while (a != null && b != null) {18            if (b.val < a.val) { tail.next = b; b = b.next; }19            else { tail.next = a; a = a.next; }   // ties take `a` → stable20            tail = tail.next;21        }22        tail.next = (a != null) ? a : b;23        return dummy.next;24    }25}

Merge runs of size 1, 2, 4, … iteratively — no recursion at all.

Count n.
For width = 1, 2, 4… < n: cut pairs of runs and merge them onto the tail.
Stop when one run covers the list.

timeO(n log n)

log n widths × one O(n) pass each.

spaceO(1)

Only a few pointers; merging just relinks nodes.

javajava.util.*

1class Solution {2    public ListNode sortList(ListNode head) {3        int n = 0;4        for (ListNode p = head; p != null; p = p.next) n++;5        ListNode dummy = new ListNode(0, head);6        for (int width = 1; width < n; width *= 2) {      // merge runs of 1, 2, 4, ...7            ListNode prev = dummy, cur = dummy.next;8            while (cur != null) {9                ListNode left = cur;10                ListNode right = cut(left, width);       // left has `width` nodes11                cur = cut(right, width);                 // right has up to `width` nodes12                prev = mergeAndAttach(prev, left, right); // returns the new tail13            }14        }15        return dummy.next;16    }17 18    /** Detaches the first `k` nodes starting at `node`; returns the head of what follows. */19    private ListNode cut(ListNode node, int k) {20        for (int i = 1; node != null && i < k; i++) node = node.next;21        if (node == null) return null;22        ListNode rest = node.next;23        node.next = null;24        return rest;25    }26 27    private ListNode mergeAndAttach(ListNode prev, ListNode a, ListNode b) {28        while (a != null && b != null) {29            if (b.val < a.val) { prev.next = b; b = b.next; }   // strictly smaller: take from b30            else { prev.next = a; a = a.next; }                 // ties take a → stable31            prev = prev.next;32        }33        prev.next = (a != null) ? a : b;                        // one run is used up: attach the other34        while (prev.next != null) prev = prev.next;             // walk to the new tail35        return prev;36    }37}

sim

Dry run: merge runs of 1, 2, 4…

loading simulation…

javajava.util.*

1class Solution {2    public ListNode sortList(ListNode head) {3        int n = 0;4        for (ListNode p = head; p != null; p = p.next) n++;5        ListNode dummy = new ListNode(0, head);6        for (int width = 1; width < n; width *= 2) {      // merge runs of 1, 2, 4, ...7            ListNode prev = dummy, cur = dummy.next;8            while (cur != null) {9                ListNode left = cur;10                ListNode right = cut(left, width);       // left has `width` nodes11                cur = cut(right, width);                 // right has up to `width` nodes12                prev = mergeAndAttach(prev, left, right); // returns the new tail13            }14        }15        return dummy.next;16    }17 18    /** Detaches the first `k` nodes starting at `node`; returns the head of what follows. */19    private ListNode cut(ListNode node, int k) {20        for (int i = 1; node != null && i < k; i++) node = node.next;21        if (node == null) return null;22        ListNode rest = node.next;23        node.next = null;24        return rest;25    }26 27    private ListNode mergeAndAttach(ListNode prev, ListNode a, ListNode b) {28        while (a != null && b != null) {29            if (b.val < a.val) { prev.next = b; b = b.next; }   // strictly smaller: take from b30            else { prev.next = a; a = a.next; }                 // ties take a → stable31            prev = prev.next;32        }33        prev.next = (a != null) ? a : b;                        // one run is used up: attach the other34        while (prev.next != null) prev = prev.next;             // walk to the new tail35        return prev;36    }37}

in the room

How to say it in the interview

talk track

Say why merge sort: no random access needed, merge is O(1) space on lists.
Code top-down first (clearer). Offer bottom-up if they push for O(1) space.

traps

Starting fast at head (not head.next) — with 2 nodes the split never shrinks → infinite recursion.
Forgetting slow.next = null — the halves stay connected.

what they ask next

Follow-ups

Merge k sorted lists (LC 23)?

Min-heap of list heads, O(N log k) — or merge pairs bottom-up, same bound.

before you submit

Edge cases to test

Empty list → return null.
Two nodes: start fast at head.next, or the split never shrinks and the recursion never ends.
Duplicates: take from the left list on ties so equal values keep their order.
5·10⁴ nodes: a recursive merge function goes one call per node deep — prefer the iterative merge with a dummy node.

practise next