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

Question

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.

Accepted Answer

A simple approach to do this is to sort the linked list using merge sort and then swap alternate nodes.
Time Complexity : O(nlogn)
The efficient approach would be to traverse the given linked list and check if current node maintains the zigzag order or not.
To check if the given node maintains zigzag order or not, a variable ind is used.
If ind = 0, then the current node’s data should be less than its adjacent node’s data.
If ind = 1, then current node’s data should be greater than its adjacent node’s data. If the current node violates the zigzag order, then swap the position of both nodes. For doing this step, maintain two pointers prev and next. prev stores previous node of current node and next stores new next node of current node.
To swap both nodes, the following steps are performed:
1. Make next node of current node, the next node of previous node.
2. Make the current node next node of its adjacent node.
3. Make current node next = next node.

Accepted Answer

Brute Force

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.

Space Complexity: O(1)Explanation:

O(1).

Since we are not using any extra space, therefore, space complexity is O(1).

Time Complexity: O(1)Explanation:

O(N ^ 2), where N is the number of nodes in the linked list.

Extracting the last node from the linked list will take linear time and we will be extracting at most N/2 times. Hence, the overall complexity will be N/2 * O(N) i.e. O(N ^ 2).

Accepted Answer

Split and Merge

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.

Space Complexity: O(1)Explanation:

O(1).

Since we are not using any extra space, therefore, space complexity is O(1).

Time Complexity: O(1)Explanation:

O(N), where N is the number of nodes in the linked list.

Finding the middle node, reversing the second half of the list, and merging the two halves, all these operations are taking linear time.