Merge Sort Linked List Problem Statement

You are given a singly linked list of integers. Your task is to sort the linked list using the merge sort algorithm.

Explanation:

Merge Sort is a divide and conquer algorithm. It divides the input into two halves, calls itself for the two halves, and then merges the two sorted halves. The merge() function is critical for merging two halves. It works by assuming that the subarrays arr[L..M] and arr[M + 1...R] are sorted and merges these two sorted subarrays into one.

Input:

The first line of input contains a single integer T, representing the number of test cases or queries to be run. 
Then the T test cases follow.

The first line of each test case contains the elements of the singly linked list separated by a single space and terminated by -1. Hence, -1 would never be a list element.

Output:

For each test case, print the sorted linked list. The elements of the sorted list should be single-space separated, terminated by -1.

The output of each test case is printed in a separate line.

Example:

To illustrate, given an input test case linked list of 3 1 2 -1, the output will be 1 2 3 -1.

Constraints:

• 1 <= T <= 10
• 1 <= N <= 10^4
• -10^9 <= data <= 10^9 and data != -1

Note:

You are not required to print the output; it has already been taken care of. Just implement the function.