Merge alternate nodes of two linked lists into the first list

Given two linked lists, merge their nodes together into first list by taking nodes alternately between the two lists. If first list runs out, remaining nodes of second list should not be moved.

 

For example, consider lists {1, 2, 3} and {4, 5, 6, 7, 8}. Merging them should result in
{1, 4, 2, 5, 3, 6} and {7, 8} respectively.
 

The solution depends on being able to move nodes to the end of a list. Many techniques are available to solve this problem: dummy node, local reference, or recursion.

 


 

Dummy Node

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, we set a to dummy.next.

 
C++ implementation –
 

Download   Run Code

Output:

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

After Merge –

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

 


 

Local References

This method uses a local reference to get rid of the dummy nodes entirely. Instead of using a dummy node, 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. It uses MoveNode() function as a helper.

 
C++ implementation –
 

Download   Run Complete Code

 


 

Recursive

The recursive solution is the most compact of all, but is probably not appropriate for production code since it uses stack space proportionate to the lengths of the lists.

 
C++ implementation –
 

Download   Run Complete Code

 

 
References:
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 🙂
 





Leave a Reply

Notify of
avatar
wpDiscuz