Rearrange Linked List Problem Statement

Given a singly linked list in the form 'L1' -> 'L2' -> 'L3' -> ... 'Ln', your task is to rearrange the nodes to the form 'L1' -> 'Ln' -> 'L2' -> 'Ln-1', etc. You must not alter the data of the nodes.

Example:

Input:

1 -> 2 -> 3 -> 4 -> 5 -> NULL

Output:

1 -> 5 -> 2 -> 4 -> 3 -> NULL

Input:

The first line contains an integer 'T' representing the number of test cases. Each test case consists of elements of the linked list separated by spaces and terminated by -1.

Output:

For each test case, output a single line of the linked list in rearranged form, separated by spaces and terminated by -1.

Constraints:

• 1 <= 'T' <= 10
• 0 <= 'L' <= 1000
• 1 <= data <= 10⁹ and data != -1

Note:

You do not need to print anything; the function implementation is required.

Follow Up:

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