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.


Download   Run Code


Download   Run Code


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).

1 Star2 Stars3 Stars4 Stars5 Stars (1 votes, average: 5.00 out of 5)


Thanks for reading.

Please use our online compiler to post code in comments. To contribute, get in touch with us.
Like us? Please spread the word and help us grow. Happy coding 🙂

Leave a Reply

newest oldest most voted
Notify of

You can also just use max-heap for this