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++ implementation –
 

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 –

 
C++ implementation using Dummy Node–
 

Download   Run Code

Output:

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

After Intersection – 4 -> 10 -> null

 


 

 
C++ implementation using Local references–
 

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 to 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 🙂