New update is available. Click here to update.

Solve problems & track your progress

Checkout your overall progress in every topic here

Become

Sensei

in DSA topics

Open the topic and solve more problems associated with it to improve your skills

Check out the skill meter for every topic

See how many problems you are left with to solve for cracking any stage. Score more than zero to get your progress counted.

Problem

Submissions

Rearrange Linked List

Contributed by

Mutiur Rehman khan

Last Updated: 23 Feb, 2023

Medium

0/80

Avg time to solve 22 mins

Success Rate 80 %

23 upvotes

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.

Detailed explanation ( Input/output format, Notes, Images )

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.

Sample Input 1 :

2
1 2 3 4 5 6 -1
1 2 -1

Sample Output 1 :

1 6 2 5 3 4 -1
1 2 -1

Explanation for sample 1:

For the first test case, we have 1 as the starting element followed by 6, 2, 5, 3 and 4 respectively in the linked list after rearrangement.

For the second test case, we will get the same linked list after rearrangement, Therefore 1 2.

Sample Input 2 :

2
2 4 6 8 10 -1
-1

Sample Output 2 :

2 10 4 8 6 -1
-1

Auto

Console