Sort linked list
Your task
Sort a singly linked list in ascending order, given as a Python list of integers, and return the sorted sequence as a Python list. You are expected to design an O(n log n) approach appropriate to a linked list (i.e. merge sort, not a comparison sort that needs random access). The list has 0 to 5*10^4 nodes and values fit in 32-bit signed range.
Examples
sort_linked_list(values: list[int]) -> list[int]Example 1
Input
sort_linked_list([4, 2, 1, 3])Output
[1, 2, 3, 4]