Given the head of a singly linked list, sort its nodes in non-decreasing order of value and return the new head. Rearrange the existing nodes rather than creating new ones or sorting a copy of the values.
Examples
Input: head = 4 -> 2 -> 1 -> 3
Output: 1 -> 2 -> 3 -> 4
Input: head = -1 -> 5 -> 3 -> 4 -> 0
Output: -1 -> 0 -> 3 -> 4 -> 5
Constraints
0 <= number of nodes <= 10**4-10**5 <= node value <= 10**5- Target: O(n log n) time; do not copy the values into a Python list and call sorted()
Goals
- Apply divide and conquer directly on nodes
- Merge two sorted chains by relinking nodes