148. Sort List
You are given head, the first node of a singly linked list. Rearrange the list so its values run in ascending order and return the head of the sorted list.
Any correct sort will be accepted, but the real target is O(n log n) time — and, if you want the full flex, constant extra memory on top of the list itself. Values can repeat and can be negative; the list has at least one node.
Example 1:
Input: head = [4, 2, 1, 3]
Output: [1, 2, 3, 4]
Explanation: Split into [4, 2] and [1, 3], sort each half into [2, 4] and [1, 3], then merge the two sorted halves into [1, 2, 3, 4].
Example 2:
Input: head = [3, -2, 0, -2, 10]
Output: [-2, -2, 0, 3, 10]
Explanation: Duplicates and negatives are handled like any other value: the sorted order is [-2, -2, 0, 3, 10].
Constraints:
- 1 ≤ number of nodes ≤ 5 * 10⁴
- -10⁵ ≤ node value ≤ 10⁵
Hints:
Heapsort and quicksort lean hard on random access, which a linked list cannot give you. Merge sort only ever walks forward — it is the natural O(n log n) sort for lists.
Find the middle with slow/fast pointers and cut the link there, sort both halves recursively, then merge two sorted lists using a dummy head. For O(1) extra space, flip it bottom-up: merge runs of length 1, then 2, then 4, … until one run covers the list.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: head = [4, 2, 1, 3]
Expected output: [1, 2, 3, 4]