Sort List
Medium · Linked Lists · Linked List · Two Pointers · Divide and Conquer · Sorting · Merge Sort
Problem
Given the head of a singly linked list, sort it in ascending order and return the head of the sorted list.
The tests build lists with from_list([...]) and read your answer back with to_list(), both already defined. Lists can be long — up to 50,000 nodes — so an O(n²) sort such as insertion sort is too slow.
Follow-up: sort in O(n log n) time using only O(1) extra memory. That rules out copying the values into an array, and it rules out recursion that goes one level deeper per node.
Examples
Input: head = 4 -> 2 -> 1 -> 3 Output: 1 -> 2 -> 3 -> 4
The same four nodes, relinked in ascending order.
Input: head = -1 -> 5 -> 3 -> 4 -> 0 Output: -1 -> 0 -> 3 -> 4 -> 5
Negative values sort before zero.
Constraints
- 0 <= number of nodes <= 5 * 10^4
- -10^5 <= Node.val <= 10^5
Approaches
- Copy the values out, sort, write them back — time O(n log n), space O(n)
Follow-up
Can you sort the list in O(n log n) time and O(1) memory (constant extra space)?
Related problems
Start free on Cariara · Coding problems · System design studio
