# 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.

## Java

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 –

## Java

Output:

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

After Intersection – 4 -> 10 -> null

## C

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.

(1 votes, average: 5.00 out of 5)

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 🙂