Sort the singly linked list in nondecreasing order and return its new head. Retain every node, including repeated values. Arrays in examples and test inputs show node values from head to tail; [] represents an empty list.
Follow-up: Can you achieve O(n log n) time using O(1) extra space?
Example 1:
Input: head = [7,2,5,2]
Output: [2,2,5,7]Explanation: Place both nodes containing 2 first, then the node containing 5, then the node containing 7. Duplicate values are retained.
Example 2:
Input: head = [-3,4,0,-1]
Output: [-3,-1,0,4]Explanation: Negative values come before zero and positive values, giving the chain -3 -> -1 -> 0 -> 4.
Example 3:
Input: head = []
Output: []Explanation: The empty list is already sorted, so return an empty list.
Constraints:
- The list contains between
0and50000nodes. -100000 <= Node.val <= 100000