Sort List
MediumP2Coding
Given the head of a singly linked list, return the list sorted in ascending order. A list node has val and next. The ListNode class is already defined for you.
Aim for O(n log n) time. Sorting by copying the values into an array is allowed to pass, but try the version that rearranges the nodes themselves.
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
- 0 <= number of nodes <= 5 * 10^4
- -10^5 <= Node.val <= 10^5
Hints
Give it a real attempt first. Run shows which examples fail.
Saved automatically
Run checks the 3 visible tests, Submit all 11. ⌘Enter runs, ⌘⇧Enter submits.