Given the head of a linked list, return the list after sorting it in ascending order.
You must solve it in O(n log n) time complexity and O(1) space complexity (ignoring recursion stack).
Example 1:
Input: head = [4,2,1,3]
Output: [1,2,3,4]
Explanation: The list is sorted in ascending order.
Example 2:
Input: head = [-1,5,3,4,0]
Output: [-1,0,3,4,5]
Explanation: Negative numbers come first, followed by the rest in order.
Example 3:
Input: head = []
Output: []
Explanation: An empty list is already sorted.
[0, 5 * 10⁴]-10⁵ <= Node.val <= 10⁵