Sort List
The key idea
Merge sort fits a linked list perfectly: splitting needs no random access (use slow/fast pointers to find the middle), and merging two sorted lists only relinks
next pointers, so no extra array is required. This gives guaranteed O(n log n) time, unlike quicksort whose pivoting needs random access.Problem
Given the head of a linked list, return the list after sorting it in ascending order.
Follow up: Can you sort the linked list in O(n log n) time and O(1) memory (i.e. constant space)?
Constraints
- The number of nodes in the list is in the range
[0, 5 * 10^4]. -10^5 <= Node.val <= 10^5
Examples
Input: head = [4,2,1,3]
Output: [1,2,3,4]
Input: head = [-1,5,3,4,0]
Output: [-1,0,3,4,5]
Input: head = []
Output: []
Complexity
Time: O(n log n) Space: O(log n)
See the full solution
- ✓Full worked approach
- ✓Reference code in 5 languages
- ✓Problem-solving tips
- ✓Step-by-step animated visualization