Rearrange Linked List

PROBLEM STATEMENT

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.

Approach 1

The main idea is to maintain a pointer ‘FRONT’ that will process the nodes from the front side of the linked list and keep removing the nodes from the backside. While removing nodes from the back, we will put them in front of the list after the ‘FRONT’ pointer and move the ‘FRONT’ pointer ahead.

Initialize the ‘FRONT’ pointer to head.
Loop till next of ‘FRONT’ pointer is not NULL
- Extract the last node from the list and insert it next to the ‘FRONT’ pointer.
- Move the ‘FRONT’ pointer to next to ‘FRONT’.
Return the ‘HEAD’ as the final result which points to the head of the newly formed linked list.

Try Problem

Approach 2

The main idea is to divide the linked list into halves and then reverse the latter half and then merge them alternatively.

First, we will find the middle node of the given linked list.
Then, we split the linked list into two halves from the middle node.
Then, the second half of the linked list is reversed.
Now, we merge the nodes of both halves alternatively to make the list into the specified form.

Try Problem