Posted: 16 Jan, 2021
Difficulty: Easy

## PROBLEM STATEMENT

#### Note

``````1. All the node values are positive.

2. The size of the linked list is greater than 1.

3. The end of the linked list is represented by -1.
``````
##### Input Format:
``````The first line of the input contains an integer T denoting the number of test cases.

The first and the only line of each test case contains the values of nodes of the linked list L, which is to be modified as shown above.
``````

#### Output format :

``````For each test case, print a single line containing space-separated integers denoting the values of the modified linked list.

The output of each test case will be printed in a separate line.
``````
##### Note:
``````You do not have to print anything, it has already been taken care of. Just implement the given function. Also, update the given linked list in place.
``````

#### Constraints:

``````1 <= T <= 50
1 <= N <= 10 ^ 4

Where 'N' is the number of nodes in a linked list.

Time Limit: 1 sec.
`````` Approach 1
• One of the important observations on which the problem is based is that we have to reverse the second half of the linked list and merge the two halves alternatively.
• Firstly, traverse till the mid point of the linked list and then reverse the linked list from mid point to the last node.
• To find the mid point of the list, we can use fast and slow pointers.
• Break the linked list at the mid point so that we will have 2 separate linked lists.