Merge given sorted linked lists into one

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 increasing order and return it.

 

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

The problem can be solved either iteratively or recursively. There are many 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’.

 


 

Using Dummy Nodes

The strategy here uses a temporary dummy node as the start of the result list. The pointer tail always points to the last node in the result list, so appending new nodes is easy. The dummy node gives tail something to point to initially when the result list is empty. This dummy node is efficient, since it is only temporary, and it is allocated in the stack. The loop proceeds, removing one node from either ‘a’ or ‘b’, and adding it to tail. When we are done, the result is in dummy.next.

 
C++ implementation –
 

Download   Run Code

Output:

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

 


 

Using Local References

This solution is structurally very similar to the above, but it avoids using a dummy node. Instead, it maintains a struct node** pointer, lastPtrRef, that always points to the last pointer of the result list. This solves the same case that the dummy node did — dealing with the result list when it is empty. If you are trying to build up a list at its tail, either the dummy node or the struct node** “reference” strategy can be used.

 
C++ implementation –
 

Download   Run Code

Output:

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

 


 

Using Recursion

Merge() is one of those nice recursive problems where the recursive solution code is much cleaner than the iterative code. You probably wouldn’t want to use the recursive version for production code however, because it will use stack space which is proportional to the length of the lists.

 
C++ implementation –
 

Download   Run Code

Output:

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

 

 
Source:
http://cslibrary.stanford.edu/105/LinkedListProblems.pdf

 
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 🙂