Description
Sort a linked list in O(n log n) time and O(1) memory. Use merge sort with bottom-up approach to achieve constant space complexity.
Examples
Input:
head = [4,2,1,3]Output:
[1,2,3,4]Explanation:
Sorted linked list.
Input:
head = [-1,5,3,4,0]Output:
[-1,0,3,4,5]Explanation:
Works with negative numbers.
Input:
head = [7,7,7,7]Output:
[7,7,7,7]Explanation:
When all elements are identical, the sorted list remains unchanged. This tests the algorithm's handling of duplicate values.
Constraints
- •
0 ≤ n ≤ 5 * 10⁴ - •
-10⁵ ≤ Node.val ≤ 10⁵