Sort Linked List Based on Actual Values

You are given a Singly Linked List of integers that is initially sorted according to the absolute values of its elements. Your task is to sort this Linked List based on the actual integer values.

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

Input:

The first line consists of a single integer ‘T’, denoting the number of test cases. Each test case includes a single line containing the elements of the singly linked list, separated by spaces, and terminated by -1. The value -1 is not part of the list data and serves as a terminator.

Output:

For each test case, provide the sorted linked list where the elements are separated by a space, ending with -1.

Example:

Input: 
1 -> -2 -> 3 -1
Output: 
-2 -> 1 -> 3 -1

Constraints:

• 1 <= T <= 10
• 1 <= N <= 5 * 10⁴
• -10⁹ <= data <= 10⁹ (data ≠ -1)
• The input list is guaranteed to be sorted based on absolute values.

Note:

The function should be implemented to sort the linked list. Output handling has been dealt with separately.