142. Sort List

Medium · Linked List

Given the head of a linked list, sort the list in ascending order and return the sorted list's head.

You must solve the problem in O(n log n) time complexity and O(log n) space complexity (due to recursion stack in merge sort). The linked list is represented as an array where each element is a node value; null represents the end of the list.

Examples

Example 1
Input: [4, 2, 1, 3]
Output: [1, 2, 3, 4]
Explanation: The unsorted list 4→2→1→3 is sorted to 1→2→3→4.
Example 2
Input: [-1, 5, 3, 4, 0]
Output: [-1, 0, 3, 4, 5]
Explanation: The list with negative numbers is sorted in ascending order.

Constraints