Rearrange Linked List

You have been given a singly Linked List in the form of 'L1' -> 'L2' -> 'L3' -> ... 'Ln'. Your task is to rearrange the nodes of this list to make it in the form of 'L1' -> 'Ln' -> 'L2' -> 'Ln-1' and so on. You are not allowed to alter the data of the nodes of the given linked list.

For example:

If the given linked list is 1 -> 2 -> 3 -> 4 -> 5 -> NULL.

Then rearrange it into 1 -> 5 -> 2 -> 4 -> 3 -> NULL. 

Input format :

The first line of input contains an integer 'T' representing the number of test cases. Then the test case follows.

The only 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 format :

For each test case, Print a single line containing the linked list in the specified form. The elements of the linked list must be separated by a single space and terminated by -1.

Note :

You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints :

1 <= 'T' <= 10
0 <= 'L' <= 1000
1 <= data <= 10 ^ 9 and data != -1

Where ‘T’ is the number of test-cases and ‘L’ is the number of nodes in the Linked List, and ‘data’ is the data in each node of the list.

Time Limit: 1 sec.

Follow Up:

Try to solve this problem in O(N) time complexity and O(1) space complexity.