Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding
Ninjas X Naukri.com

Last Updated: 4 Dec, 2020

Easy

```
If the given list is {1 -> -2 -> 3} (which is sorted on absolute value), the returned list should be {-2 -> 1 -> 3}.
```

```
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.
It is guaranteed that the given list is sorted based on absolute value.
```

```
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 don't need to print the output, it has already been taken care of. Just implement the given function.
```

```
1 <= T <= 10
1 <= 'N' <= 5 * 10^4
-10^9 <= 'data' <= 10^9 and 'data' != -1
Where 'N' denotes the number of elements in the Singly Linked List and 'data' represents the value of those elements.
Time Limit : 1 sec
```

**If ‘SORTED_LIST’ is empty or the head of the ‘SORTED_LIST’ has a value greater than the node, in this case, the current node will become the new head of ‘SORTED_LIST’.****Else, we will traverse the ‘SORTED_LIST’ until we find the node that has a value greater than the current node or until we reach the end.****We will insert the node at this position and change it’s ‘next’ value such that it points to the node which is greater than the current node.**

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.

- 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 make a list ‘MERGE_LIST’ which will be initially empty. If the head of the first sublist has a value less than the head of the second sublist then we will add the head of the first sublist in the ‘MERGE_LIST’ and change the head to its next value. Else, we will add 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’.

In the given list all non-negative values are present in sorted order but all negative values are present in reverse order. We have to reverse the negative values and move it before the first non-negative value.

For example, say the given list is {0-> 1 -> -2 -> 3 -> -4}. In this list, non-negative values {0, 1, 3} are present in sorted order and the negative values {-2, -4} are present in reverse order.

So, we traverse the list and if we encounter a negative value node, we will move this node before the head node and this node will become the new head of the list. After doing this for all negative values, we will have a sorted list.

Similar problems

Max Prefix

Easy

Posted: 31 Oct, 2022

Merge Two Sorted Arrays Without Extra Space

Moderate

Posted: 19 Nov, 2022

Merge Two Sorted Arrays Without Extra Space

Moderate

Posted: 19 Nov, 2022

Delete Nodes On Regular Intervals

Ninja

Posted: 19 Dec, 2022

Add One To Linked List

Hard

Posted: 19 Dec, 2022

Sort 0s, 1s, 2s

Easy

Posted: 24 Dec, 2022