Intersection of two given sorted linked lists

Given two lists sorted in increasing order, create and return a new list representing the intersection of the two lists. The new list should be made with its own memory — the original lists should not be changed.

 

For example,

Input:
First List  : 1 -> 4 -> 7 -> 10 -> null
Second List : 2 -> 4 -> 6 -> 8 -> 10 -> null

Output: 4 -> 10 -> null

 


 

The strategy is to advance up both lists and build the result list as we go. When the current point in both lists are the same, add a node to the result. Otherwise, advance whichever list is smaller. By exploiting the fact that both lists are sorted, we only traverse each list once.

C++

Download   Run Code


Output:

First List  – 1 -> 4 -> 7 -> 10 -> null
Second List – 2 -> 4 -> 6 -> 8 -> 10 -> null

After Intersection – 4 -> 10 -> null

 


 

To build up the result list, both the dummy node and local reference strategy can be also used. These solutions are shown below –

 

Implementation using Dummy Node –

C++

Download   Run Code


Output:

First List  – 1 -> 4 -> 7 -> 10 -> null
Second List – 2 -> 4 -> 6 -> 8 -> 10 -> null

After Intersection – 4 -> 10 -> null

 


 

Implementation using Local references –

 

C++

Download   Run Code


Output:

First List  – 1 -> 4 -> 7 -> 10 -> null
Second List – 2 -> 4 -> 6 -> 8 -> 10 -> null

After Intersection – 4 -> 10 -> null

 

Exercise: Write recursive solution for this problem.
 

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 🙂
 





Leave a Reply

Notify of
avatar
Sort by:   newest | oldest | most voted
AllergicToBitches
AllergicToBitches

nice.. I have implemented without using dummy node
http://ideone.com/zhqRPZ

wpDiscuz