Sort Linked List

Given the head of a singly linked list, sort the list in ascending order and return the sorted list's head.

You must solve it in O(n log n) time and, ideally, using O(1) extra space (not counting the recursion stack), which rules out dumping the values into an array, sorting the array, and rebuilding the list.

Example 1

Input: head = [4, 2, 1, 3]
Output: [1, 2, 3, 4]

Example 2

Input: head = [-1, 5, 3, 4, 0]
Output: [-1, 0, 3, 4, 5]

Example 3

Input: head = []
Output: []

Constraints

• The number of nodes is in the range [0, 5 * 10^4].
• -10^5 <= Node.val <= 10^5