Sort List
Given the head of a linked list, sort it in ascending order in O(n log n) time and O(1) (or O(log n)) space.
- The number of nodes in the list is in the range [0, 5 * 10⁴].
- -10⁵ <= Node.val <= 10⁵
Intuition
Sort list leetcode problem 148 sorts a linked list in O(n log n) time with constant extra space. Those two requirements together decide the algorithm. Quicksort is poor here — a linked list has no random access, so choosing a pivot and partitioning costs far more than on an array, and the worst case is O(n²). Merge sort is the natural fit: - Merge sort needs only sequential access and merges without extra storage, since linked nodes can be relinked rather than copied. On an array, merging requires a temporary buffer. On a list it does not, which is the one case where linked structures beat arrays outright. The algorithm splits the list at the middle, sorts each half recursively, and merges the sorted halves. Finding the middle uses the two-speed walk. The critical step afterwards is severing the halves — setting the first half's tail to null. Leaving them connected means the recursion never shrinks the input and the sort loops forever. The base case is a list of zero or one nodes, which is already sorted. Missing it produces infinite recursion on the smallest inputs. Merging two sorted lists is the standard routine, cleanest with a dummy head so every append is uniform, and the remainder attached in one assignment. Strictly, top-down merge sort uses O(log n) stack space rather than O(1). The bottom-up variant merges sublists of size 1, 2, 4, and so on iteratively, achieving genuine O(1) space — worth knowing when the constraint is taken literally. Sorting gives O(n log n) time with O(log n) stack space, or O(1) bottom-up.
When asked to sort a linked list in O(n log n), merge sort is the go-to. The two core operations — find midpoint (slow/fast pointers) and merge two sorted lists — are standard linked list primitives. Quicksort is harder on linked lists because random-access pivoting is expensive. If the problem requires O(1) space, bottom-up merge sort avoids the O(log n) recursion stack.
Approach
Before reading on: price up what the direct approach costs here, then ask which pointers must be saved before you overwrite anything. Aim for O(n log n) time and O(log n) space.
Choose merge sort deliberately
A linked list has no random access, so quicksort's partitioning is costly and its worst case O(n²). Merge sort needs only sequential access.
Note the merging advantage
Merging linked nodes needs no temporary buffer — nodes are relinked rather than copied. This is the one case where lists beat arrays outright.
Handle the base case
A list of zero or one nodes is already sorted. Omitting this causes infinite recursion on the smallest inputs.
Split at the middle
Use the two-speed walk to locate the midpoint, then divide the list into two halves for independent sorting.
Sever the two halves
Set the first half's tail to null. Leaving them connected means the recursion never shrinks the input and the sort never terminates.
Merge with a dummy head
Compare heads, take the smaller, and attach the remainder in one assignment. The dummy makes every append uniform.
Cost of the sort
O(n log n) time with O(log n) stack space top-down. The bottom-up variant merges sublists iteratively for genuine O(1) space.
Solution & live demo
Common pitfalls
Not cutting the list at the midpoint before recursing
mid = slow return merge(sortList(head), sortList(mid))
prev.next = None return merge(sortList(head), sortList(slow))
Without cutting, the left half still points to the right half. The left recursive call processes the entire list, causing infinite recursion.
Finding the wrong midpoint for a two-element list
while fast and fast.next:
slow = slow.next
fast = fast.next.nextwhile fast.next and fast.next.next:
slow = slow.next
fast = fast.next.nextFor a two-element list A -> B, the first version leaves slow at B (the second node), making the left half the entire list and the right half empty — infinite recursion. The second version keeps slow at A, splitting into [A] and [B].
Not handling the base case for a single node
if not head:
return headif not head or not head.next:
return headA single node has no pair to split into. Without the not head.next check, the function tries to find a midpoint of a one-element list, and depending on the splitting logic, may recurse infinitely.
Edge cases
Base case returns None immediately.
Base case returns the node as-is. No splitting or merging.
Merge sort still splits and merges, but the merge step degenerates to appending one half after the other. Same O(n log n) time.