Linked ListMerge SortDivide and Conquer
Sort a linked list in ascending order in O(n log n) time. Arrays can be sorted with random access, but a linked list cannot, so think about which sorting algorithm suits it. The values are given as an array; build the linked list from them yourself, then solve it with pointers.
Input
Line 1: n. Line 2: the n node values.
Output
Print the sorted values on one line.
Constraints
1 <= n <= 5 * 10^4 -10^5 <= value <= 10^5
Example 1
Input
4 4 2 1 3
Output
1 2 3 4
Sorted ascending: 1 2 3 4.