For a given Singly Linked List of integers, sort the list using the 'Merge Sort' algorithm.
The first and the only line of input contains the elements of the linked list separated by a single space.
While specifying the list elements for input, -1 indicates the end of the singly linked list and hence, would never be a list element
The only line of output contains the sorted elements of the Singly Linked List in a row, separated by a single space.
You are not required to print the elements, just sort the elements and return the head to the updated Singly Linked List.
1 <= N <= 10^5
1 <= DATA <= 10^9
Where 'DATA' denotes the value of node of Linked List.
Time Limit: 1sec
1 4 5 2 -1
1 2 4 5
10 9 8 7 6 5 4 -1
4 5 6 7 8 9 10