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

 
1 Star2 Stars3 Stars4 Stars5 Stars (1 votes, average: 5.00 out of 5)

Loading...

Thanks for reading.

Please use our online compiler to post code in comments. To contribute, get in touch with us.
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