Modify Linked list

Easy
0/40
Average time to solve is 10m
11 upvotes
Asked in companies
Dream11FacebookIBM

Problem statement

You are given a linked list containing N nodes where each node is associated with a certain value. Return a linked list as follows: If the input linked list is 1-->2-->3-->4, then the output should be 1-->4-->2-->3. And if the input is 1-->2-->3-->4-->5, then the output should be 1-->5-->2-->4-->3.

In other words, if the original linked list is first -> second -> third -> ……….->thirdlast -> secondlast -> last, then the modified linked list would be first -> last -> second -> second_last -> ...

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.
Detailed explanation ( Input/output format, Notes, Images )
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.
Sample Input 1:
2
1 2 3 4 -1
1 2 3 4 5 -1
Sample Output 1:
1 4 2 3
1 5 2 4 3

Explanation of Sample Input 1:

Test case 1:
The original Linked List  1 -> 2 -> 3 -> 4 is modified to 1 -> 4 -> 2 -> 3

Test case 2:
The original Linked List  1 -> 2 -> 3 -> 4 ->5 is modified to 1 -> 5 -> 2 ->4 ->3
Sample Input 2:
4
1 2 3 4 5 6 -1
1 -1
1 2 -1 
1 2 3 -1
Sample Output 2:
1 6 2 5 3 4 
1 
1 2 
1 3 2
Hint

Reversing the other half of the list may help?

Approaches (1)
Implementation
  • 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.
  • Let head1 be the pointer which points at the head of the first linked list and head2 be the pointer which points at the head of the second linked list.
  • Now merge both of the linked lists alternatively to get the final desired output. Look at the code below.

 

Where head1 is the head of the first list and head2 is the head of the second list.

  • For e.g., if the input linked list was 1, 2, 3, 4. After reversing the second half and creating two different linked lists we will have head1 = 1, 2 and head2 = 3, 4.
  • We have to merge these two linked lists alternatively and we get our final linked list as :  1, 3, 2, 4.
Time Complexity

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

 

We first do O(N) iterations to find the middle, then we do O(N) iterations to reverse the second half, and finally, we do O(N) iterations to merge the list. So our overall Time Complexity is O(N).

Space Complexity

O(1).

 

Since we are using constant extra space.

Code Solution
(100% EXP penalty)
Modify Linked list
Full screen
Console