Merge two sorted linked lists from their end

Write a function that takes two lists, each of which is sorted in increasing order, and merges the two together into one list which is in decreasing order and return it. In other words, merge two sorted linked lists from their end.

 

For example, consider lists {1, 3, 5} and {2, 6, 7, 10}. Merging them should yield
{10, 7, 6, 5, 3, 2, 1}.
 

 


 

There are few cases to deal with: either ‘a’ or ‘b’ may be empty, during processing either ‘a’ or ‘b’ may run out first, and finally there’s the problem of starting the result list empty, and building it up while going through ‘a’ and ‘b’.

 

We can easily solve this problem by using MoveNode() function as a helper which takes the node from the front of the source, and move it to the front of the destination. Rest of the code remains similar to merge() process of Merge Sort.

 
C++ implementation –
 

Download   Run Code

Output:

First List – 2 -> 4 -> 6 -> null
Second List – 1 -> 3 -> 5 -> 7 -> 9 -> null

After Merge – 9 -> 7 -> 6 -> 5 -> 4 -> 3 -> 2 -> 1 -> 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 🙂
 





Leave a Reply

Notify of
avatar
Sort by:   newest | oldest | most voted
P G
Guest

You can also just use max-heap for this

wpDiscuz