Sort a linked list
Mediumlinked listsortingmerge sortdivide and conquer
Sort the list in ascending order in O(n log n) time. Don't copy the values into an array; sort 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]
Constraints
- 0 ≤ number of nodes ≤ 5·10⁴
- -10⁵ ≤ Node.val ≤ 10⁵
Submit checks your solution against 9 tests, including hidden ones.
// Provided by the judge: keep these definitions
class ListNode {
constructor(val = 0, next = null) {
this.val = val
this.next = next
}
}
/**
* @param {ListNode|null} head
* @return {ListNode|null}
*/
function sortList(head) {
}