359. Sort Linked List (Merge Sort)

Given the head of a linked list, return the list sorted in ascending order. Aim for O(n log n) time. The list is given as an array; return the sorted array.

Input: An array of node values.

Output: Array — the sorted list.

Examples

Input: [4,2,1,3]
Output: [1,2,3,4]
Explanation: Sorted ascending.

Input: [-1,5,3,4,0]
Output: [-1,0,3,4,5]
Explanation: Includes negatives.

Input: []
Output: []
Explanation: Empty list.

Constraints

• 0<=n<=5*10^4
• -10^5<=value<=10^5

Asked by