Rearrange linked list in specific manner in linear time

Given a linked list, rearrange the nodes in specific way in linear time and constant space. The alternate positions in the output list should be filled with the nodes starting from the beginning and from the very end of the original list respectively.

 

For example,

Input  : 1 -> 2 -> 3 -> 4 -> 5 -> 6
Output : 1 -> 6 -> 2 -> 5 -> 3 -> 4
 

Input  : 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7
Output : 1 -> 7 -> 2 -> 6 -> 3 -> 5 -> 4

 


 

We can easily solve this problem by dividing it into three subproblems –

  • Divide the list into two equal parts.
     
  • Reverse the second half.
     
  • Merge second half into first half at alternate positions. Use of extra space is not allowed (Not allowed to create additional nodes), i.e., insertion must be done in-place.
     

C++ implementation –
 

Download   Run Code

Output:

1 -> 6 -> 2 -> 5 -> 3 -> 4 -> null

 

The time complexity of above solution is O(n).
 

 
Thanks for reading.




Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂