Rearrange the linked list so that it has alternating high, low values

Given an linked list of integers, rearrange it such that every second node of the linked list is greater than its left and right nodes. In other words, rearrange linked list node in alternating high-low.

 

Assume no duplicate nodes are present in the linked list. Several lists might satisfies the constraints, we need to print any one of them. For example,


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

Input:  9 -> 6 -> 8 -> 3 -> 7
Output: 6 -> 9 -> 3 -> 8 -> 7
 

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

 


 

The idea is to start from the second node in the linked list and advance two nodes at a time for each iteration of loop. If previous node is greater than the current node, we swap their values. Similarly, if next node is greater than the current node, we swap both values. At the end of loop, we will get the desired linked list that satisfies given constraints.

C++

Download   Run Code

Output:

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

 
The time complexity of above solution is O(n) and auxiliary space used by the program is O(1).

 
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 🙂
 


Get great deals at Amazon




Leave a Reply

avatar
  Subscribe  
Notify of