Sort a Singly Linked List

Given the head of a singly linked list, sort the list in ascending order.

You are required to implement a merge sort algorithm for the linked list with a time complexity of (O(n \log n)). The main idea is to split the list into two halves, recursively sort each half, and then merge them back together.

For example, if the input list is [4, 2, 1, 3], the correctly sorted output is [1, 2, 3, 4].

inputFormat

The first line of input contains an integer (n) representing the number of elements in the linked list. The second line contains (n) space-separated integers representing the node values. If (n = 0), the list is empty.

outputFormat

Output the sorted linked list values in ascending order, separated by a single space. If the list is empty, output nothing.## sample

4
4 2 1 3

1 2 3 4