MergeSort Linked List Problem Statement

You are given a Singly Linked List of integers. Your task is to sort the list using the 'Merge Sort' algorithm.

Input:

The input consists of a single line containing the elements of the linked list separated by a single space.

Output:

The output is a single line containing the sorted elements of the Singly Linked List in a row, separated by a single space.

Example:

Input:

4 3 2 1 -1 

Output:

1 2 3 4

Constraints:

• 1 <= N <= 10^5
• 1 <= DATA <= 10^9
• Time Limit: 1 second

Note:

-1 indicates the end of the singly linked list and is not an element of the list.

You do not need to print anything; only sort the elements and return the head of the updated Singly Linked List.