Sort a Linked List
Advanced
Sort the list in increasing order and return its head. Aim for O(n log n) time.
The starter code is an insertion sort. It is correct but too slow for long lists.
The tests show a list as a Python list of its values: [1, 2, 3] stands for 1 -> 2 -> 3.
Examples
Example 1
Input:
sort_list(head) # head = 4 -> 2 -> 1 -> 3
Output:
[1, 2, 3, 4]
Example 2
Input:
sort_list(head) # head = -1 -> 5 -> 3 -> 4 -> 0
Output:
[-1, 0, 3, 4, 5]
Constraints
0 <= number of nodes <= 100000-10**9 <= val <= 10**9
Theory
Go to TheoryKeywords
dsa-sheetlinked-listpointer-tricks
Run your code to see results
No results yet
Run your code to check it against the examples, or submit to run every test.