A warehouse ingest appends each scan as a node the moment the belt sees it — a singly linked list in arrival order, not tracking-id order. Dispatch wants the chain sorted by id before the picker walk, without a second pile of package objects. The intern copied every val into an ArrayList, called Collections.sort, and wrote the numbers back onto the same nodes. Thirty packages in staging came back sorted. A peak shift with a few hundred thousand scans allocated a second array of integers while the SLA still said extra space besides the call stack. The numbers were right. The bill was not.
Sort List asks you to return the head of the same nodes, now in ascending order, in O(n log n) time. This is an interview writeup, not a merge-sort lecture. The linked list post owns splice and why get(i) walks. Merge sort already owns split, recurse, and merge on arrays — including the extra aux buffer. Here we only care about applying that tree to nodes: there is no random-access mid index, so you find a middle and cut; there is no aux, so you merge two sorted lists by rewiring next.
The problem
Given the head of a singly linked list, sort it in ascending order and return the new head. Empty and one-node lists are already sorted. The interview bound is O(n log n) time and O(1) extra space — or O(log n) if the sort is recursive.
4 → 2 → 1 → 3 → null → 1 → 2 → 3 → 4 → null
-1 → 5 → 3 → 4 → 0 → null → -1 → 0 → 3 → 4 → 5 → null
1 → null → 1 → null
empty → emptyA node is the usual two fields:
final class ListNode {
int val;
ListNode next;
ListNode(int val) {
this.val = val;
}
}Note: In-place here means the same node objects, new next links. Writing sorted values back onto those objects keeps identity and still spends a linear buffer. Insertion sort splices with O(1) extra and pays O(n²). Neither is the bound they asked for.
Copy, sort, write back is the honest extra-space brute
Walk once, collect every val, sort the array, write the sorted numbers onto the original nodes in order. The chain’s identity is unchanged. You bought random access you did not have.
ListNode sortByCopy(ListNode head) {
List<Integer> vals = new ArrayList<>();
for (ListNode n = head; n != null; n = n.next) {
vals.add(n.val);
}
Collections.sort(vals);
ListNode n = head;
for (int v : vals) {
n.val = v;
n = n.next;
}
return head;
}At a handful of scans this is a rounding error. At belt scale you paid O(n) extra integers for a question merge sort already answers by splicing. Insertion sort — walk each node into a growing sorted prefix — is the other honest brute: O(1) extra, O(n²) splices, and still misses the bound.
Split at the first middle, cut, recurse, merge
Merge sort is still split, sort each half, merge. On an array the split is an index. On a singly list the split is a pointer, and the two halves stay one list until you cut.
Base case: null or a single node is sorted. Otherwise:
- First middle, not the sibling’s second. Middle of the Linked List parks slow on the second middle when the length is even. Paste that loop on two nodes and slow lands on the last node: the cut writes
nullonto a tail that was alreadynull, andsortList(head)still sees both nodes. On4 → 2 → 1 → 3it sits on1(left three, right one), and that three-node half later hits the same two-node trap. Merge sort wants the first of the two middles so the left half is shorter-or-equal and every split shrinks. Same 2:1 ratio; stop one step earlier: loop whilefast.nextandfast.next.nextare both non-null. Odd length still lands on the single middle (it stays with the left half). - Cut. Save
right = slow.next, thenslow.next = null. Skip the cut andsortList(head)still sees the whole chain. The recursion never shrinks. You do not return. - Merge the sorted halves. Merge Two Sorted Lists is the combine step. Call it.
Walk 4 → 2 → 1 → 3. Even length is the length that never shrinks if you skip the cut:
sort(4 → 2 → 1 → 3)
first middle:
start: slow=4 fast=4
step 1: slow=2 fast=1 fast.next.next is null, stop
cut: 4 → 2 → null right = 1 → 3
sort(4 → 2)
first middle is 4; cut: 4 → null right = 2
merge(4, 2) → 2 → 4
sort(1 → 3)
first middle is 1; cut: 1 → null right = 3
merge(1, 3) → 1 → 3
merge(2 → 4, 1 → 3) → 1 → 2 → 3 → 4Leave 2.next pointing at 1 and the left recursive call is still 4 → 2 → 1 → 3. Same n. Same split. Stack until the process dies.
Odd length 4 → 2 → 1 → 3 → 0 keeps the middle on the left:
start: slow=4 fast=4
step 1: slow=2 fast=1
step 2: slow=1 fast=0 fast.next is null, stop
cut: 4 → 2 → 1 → null right = 3 → 0The Java is that tree. mergeTwoLists is the sibling splice — leftover attach included.
ListNode sortList(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode slow = head;
ListNode fast = head;
while (fast.next != null && fast.next.next != null) {
slow = slow.next;
fast = fast.next.next;
}
ListNode right = slow.next;
slow.next = null;
ListNode leftSorted = sortList(head);
ListNode rightSorted = sortList(right);
return mergeTwoLists(leftSorted, rightSorted);
}
ListNode mergeTwoLists(ListNode a, ListNode b) {
ListNode dummy = new ListNode(0);
ListNode 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;
return dummy.next;
}Time is O(n log n) — Θ(log n) split levels, each node merged once per level, the same leading term the array post already named. Extra space is O(log n) for the call stack, and no auxiliary array of values. Interviewers who say O(1) extra usually mean “no aux.” Say the stack out loud. A bottom-up pass (run width 1, 2, 4, …) drops the recursion; that is a follow-up, not the default sketch.
Empty and one node hit the base case and never split. Two nodes: the middle loop never runs, you cut after the first, merge two singletons, you return the smaller head. The sibling loop would take that step, land on the tail, and recurse on the same pair.
Cut slow.next before you recurse. Forgetting the write is infinite recursion, not a wrong order. Dropping the base case on a one-node list is the same bug: slow never moves, right is null, you recurse on head again.
Note: <= in the merge takes the left run on a tie, the same left-on-tie rule merge sort uses for stability. Either side stays sorted; pick one and stick to it.
What interviewers usually poke next
- True
O(1)extra. Bottom-up: merge adjacent runs of width1, then2, then4, until one run covers the list. Same splice, no call stack. Say it exists; do not derail the recursive sketch unless they ask you to write it. - Why not the middle writeup’s loop? That loop returns the second middle. On two nodes slow is the tail, the cut does not detach, and you recurse on the same pair. On four nodes left is three. You can keep a
prevbehind slow and cutprev.nextinstead. Say which middle the split needed before you copy the sibling condition. - Merge k Sorted Lists. A heap of current heads, pairwise this merge, or a tournament of lists. Same splice, more sources. That problem lives with heaps, not in this folder.
- Why not quicksort? Partition wants a pivot swap you do not have as
a[i]. You can still partition by splicing, and you still risk a hostile pivot. Merge sort is the list-nativeO(n log n)because the combine step is already a linear splice. - Already sorted / reversed. Still
Θ(n log n)splits and merges, same as the array procedure. Insertion sort would be cheap on nearly-sorted input and still fails the bound on the reversed belt. - Do it by copying values. Correct numbers if you write back, extra space, and you sorted integers rather than the list. Say why the splice is the bill they asked for.
You are done with this problem when you can sort 4 → 2 → 1 → 3 on a whiteboard by cutting after 2, and you can name the infinite recursion that happens if 2.next still points at 1.