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

Java

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

Java

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

avatar
  Subscribe  
newest oldest most voted
Notify of
AllergicToBitches
Guest

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