Sort Linked List Based on Actual Values

Given a Singly Linked List of integers that are sorted based on their absolute values, the task is to sort the linked list based on the actual values.

The absolute value of a real number x, denoted |x|, is the non-negative value of x without regard to its sign.

Example:

Input:

{1 -> -2 -> 3}

Output:

{-2 -> 1 -> 3}

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

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.

Constraints:

• 1 <= T <= 10
• 1 <= 'N' <= 5 * 104
• -109 <= 'data' <= 109 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

Note :

You don't need to print the output, it has already been taken care of. Just implement the given function.