DSA problem
Sort List
Given the head of a linked list, return the list after sorting it in ascending order. You should aim for O(n log n) time complexity, ideally with O(1) extra space beyond the recursion stack.
Sorting a linked list is interesting precisely because the data structure does not support random access. Algorithms like quicksort and heapsort, which depend on cheap indexing, do not translate well. Merge sort, by contrast, is a perfect fit: its merge step only requires sequential walking of two sorted lists, and the divide step is just a list split.
The recipe is the standard divide-and-conquer template adapted to pointers. First, find the midpoint of the list using the classic slow / fast pointer technique — slow advances one step while fast advances two; when fast falls off the end, slow sits on the middle. Cut the list there by setting slow.next = null, which gives you two independent half-lists. Recurse on each half to sort it, then call a standard linked-list merge that walks two sorted lists and weaves them together using a dummy node.
The recursion has depth O(log n) and each level of recursion processes all n nodes during the merges, so total time is O(n log n). Stack usage is O(log n) for the recursive variant; a fully iterative bottom-up version can drop that to O(1). This implementation shows the cleaner recursive form, which is the version interviewers usually want to see explained.
Examples
head = [4,2,1,3][1,2,3,4]head = [-1,5,3,4,0][-1,0,3,4,5]head = [][]Constraints
- The number of nodes in the list is in the range [0, 5 * 10^4].
- -10^5 <= Node.val <= 10^5
- Target time complexity is O(n log n).
- Solutions are expected to run in O(log n) stack space (recursive) or O(1) space (iterative bottom-up).
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.