New update is available. Click here to update.

Last Updated: 3 Dec, 2020

Moderate

```
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.
```

```
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.
```

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

```
1 <= T <= 10
1 <= N <= 10^4
-10^9 <= data <= 10^9 and data != -1
Where data is the value associated with the node.
Time Limit: 1 sec
```

Approaches

We will use the βMerge Sortβ algorithm to sort the given linked list. Merge Sort is a Divide and Conquer algorithm. In this algorithm, we will divide the list into two parts, recursively sort the two parts and finally merge them such that the resultant list will be sorted.

**Algorithm:**

- If the list contains only one node, return the head of the list.
- Else, divide the list into two sublists. For this, we will take pointers βMIDβ and βTAILβ which will initially point to the head node. We will change βMIDβ and βTAILβ as follows until βTAILβ becomes NULL:

βMIDβ = βMIDβ -> next

βTAILβ = βTAILβ -> next -> next.

The above operation will ensure that βMIDβ will point to the middle node of the list. βMIDβ will be the head of the second sublist, so we will change the βNEXTβ value of the node which is before mid to NULL.

- Call the same algorithm for the two sublists.
- Merge the two sublists and return the head of the merged list. For this, we will take a pointer to a node, βMERGE_LISTβ, which will be initially pointing to NULL. If the head of the first sublist has a value less than the head of the second sublist then we will point the βMERGE_LISTβ to the head of the first sublist and change the head to its next value. Else, we will point the βMERGE_LISTβ to the head of the second sub list.
- In the end, if any of the sublists becomes empty and the other sublist is non-empty, then we will add all nodes of the non-empty sublist in the 'MERGE_LISTβ.