**Difficulty:** Medium**, Asked-in:** Amazon, Microsoft, Yahoo

**Key takeaway:** An excellent problem to learn problem-solving using two-pointers in a linked list.

Given two sorted linked lists, write a program to return the intersections of the linked lists.

- We need to return the head pointer of the new linked list.
- Both linked lists have no cycle.
- If there is no common element, then we return NULL.
- We shouldn’t do any changes in the structure of the linked lists.

**Example 1**

Input: list1 = **2** -> **9** -> 13 -> **20** -> 22 -> **27** -> NULL, list2 = **2** -> 4 -> **9** -> **20** -> **27** -> NULL

Output: 2 -> 9 -> 20 -> 27 -> NULL

Explanation: 2, 9, 20, and 27 are the common nodes to both linked lists.

**Example 2**

Input: list1 = 13 -> 22 -> 27 -> NULL, list2 = 4 -> 23 -> NULL

Output: NULL

Explanation: No nodes are common to both linked lists.

**Important note:** before moving on to the solutions, we recommend trying this problem on paper for atleast 15 or 30 minutes. Enjoy problem-solving!

- Two pointers approach using head and tail pointers
- An implementation using dummy node
- An implementation using local references
- Recursive version of the iterative approach

**Solution idea**

Both linked lists are sorted in increasing order. How can we use this information to find the common node to both linked lists? Let's think!

One idea is: common nodes will be present in the same order in both sorted linked lists. For example: if one linked list is 2->7->9->12 ->17->NULL and other linked list is 1->7->12->15->17->NULL, then the order of common nodes will be the same i.e. (7, 12, 17).

So using the sorted order property, we can scan both lists from the start, compare values one by one and generate the intersection list. When both node values are the same, we add that node to the output. Otherwise, whichever node value is smaller, we move forward in that list to search for the next value of the intersection. Think!

At any general point, suppose we are at a node x in list1 and node y in list2.

**If(x->data == y->data):**both values are common, so we add any one of the nodes to the output. Now we move forward in both linked lists to find the other common nodes.**If(x->data > y->data):**the node with value y is not be present in list1. In other words, it will not be part of the output because the value of nodes present after x in list1 will be greater than y. So, we move forward in list2 to search node x. Think!**If(x->data < y->data):**the node with value x will not be present in list2. In other words, it will not be part of the output because the value of nodes present after y in list2 is already greater than x. So we move forward in the list1 to search node with the value y.

**Solution steps**

Suppose we are using a function **listIntersection(ListNode list1, ListNode list2),** which takes heads of the linked list as an input and returns the head of the intersection linked list.

Step 1: We initialize two pointers **intersecHead** and **intersecTail** with NULL.

- intersecHeadwill track the head of the intersection
- intersecTail will track the last node of the intersection.

Step 2: We run a loop till we reach the end of any one of the linked lists i.e. **while (list1 != NULL && list2 != NULL)**. At each step of the iteration:

**If (list1->data == list2->data):**We create a new node equal to the value of the common node, insert it after the intersecTail pointer, and increment list1 and list2 to the next node. Note: If it is the first common node, we also update the intersecHead pointer with that node.**If (list1->data < list2->data):**We move the list1 pointer to the next node.**If (list1->data > list2->data):**We move the list2 pointer to the next node.

Step 3: By the end of the loop, we return the **intersecHead** as an output.

**Solution pseudocode**

```
ListNode listIntersection(ListNode list1, ListNode list2)
{
ListNode intersecHead = NULL
ListNode intersecTail = NULL
while (list1 != NULL && list2 != NULL)
{
if (list1->data == list2->data)
{
if (head == NULL)
{
intersecHead = new ListNode(list1->data)
intersecTail = intersecHead
}
else
{
intersecTail->next = new ListNode(list1->data)
intersecTail = intersecTail->next
}
list1 = list1->next
list2 = list2->next
}
else if (list1->data < list2->data)
list1 = list1->next
else
list2 = list2->next
}
return intersecHead
}
```

**Solution analysis**

In the worst-case scenario, we traverse each node of both linked lists at least once and perform an O(1) operation. If the length of both linked lists is m and n, then time complexity = (m + n) * O(1) = O(m + n). Space complexity = O(1), as we are using a constant number of variables.

**Solution idea**

This strategy is similar to the above approach, but we use a temporary **dummy** node as the start of the output list. Here dummy->next would be the head node, which we return as an output.

We also use an **intersecTail** pointer which points to the last node in the output list, so appending new nodes will be easy at the end. The dummy node gives the tail something to point initially when the output list is empty! Think!

**Solution steps**

- We create a
**dummy**node. - We create a pointer
**intersecTail**and initialize it with the dummy node. - Now we traverse both linked lists using a loop similar to the above approach.
**If (list1->data == list2->data)**, we add common elements to the end of the intersecTail pointer. Otherwise, we perform similar operations used in the above approach.- By the end of the loop, we return the next node of the dummy node.

**Solution pseudocode**

```
ListNode listIntersection(ListNode list1, ListNode list2)
{
ListNode dummy = new ListNode()
ListNode intersecTail = dummy
while (list1 != NULL && list2 != NULL)
{
if (list1->data == list2->data)
{
intersecTail->next = new ListNode(list1->data)
intersecTail = intersecTail->next
list1 = list1->next
list2 = list2->next
}
else if (list1->data < list2->data)
list1 = list1->next
else
list2 = list2->next
}
return dummy->next
}
```

**Solution analysis**

We are using the loop idea similar to the above approach. So the time and space complexity will be the same in the worst-case. Time complexity = O(m + n) and Space complexity = O(1).

**Solution idea and steps**

This solution is also similar to the above approach, but we avoid using a dummy node. Instead, we maintain a pointer **lastNodeRef**, that always points to the last pointer of the output list. So whenever we found a common node in list1 and list2, we add the common node to the end of the output list using the helper function **insertAtEnd(list1->data, lastNodeRef)** and update the lastNodeRef with the new last node of the output list.

**Note:** This technique is an excellent way to explore problem-solving if you understand pointers. It will be one of the alternative solutions approaches to solve some of the advanced linked list problems.

**Solution pseudocode C++**

```
ListNode listIntersection(ListNode list1, ListNode list2)
{
ListNode intersecHead = NULL
ListNode* lastNodeRef = &intersecHead
while (list1 != NULL && list2 != NULL)
{
if (list1->data == list2->data)
{
insertAtEnd(list1->data, lastNodeRef)
lastNodeRef = &((*lastNodeRef)->next)
list1 = list1->next
list2 = list2->next
}
else if (list1->data < list2->data)
list1 = list1->next
else
list2 = list2->next
}
return intersecHead
}
void insertAtEnd(int data, ListNode *lastNodeRef)
{
ListNode newNode = new ListNode(data)
(*lastNodeRef)->next = newNode
}
```

**Solution analysis**

We are using the loop idea similar to the above approach and the time complexity of the insertAtEnd() is O(1). So time and space complexity will be the same in the worst-case. Time complexity = O(m + n). Space complexity = O(1).

**Solution idea and steps**

Can we solve the problem using the solution of the smaller problem? Let's think!

Suppose our initial function call is **listIntersection(list1, list2),** then there will be three scenarios to build the recursive solution:

**If (list1->data = list2->data)**: Head nodes are common to both lists, and we add any one of the nodes to the intersection. Now, the problem gets reduced to find the intersection of the remaining list of sizes**m - 1**and**n - 1**. So our function call for smaller sub-problem is**listIntersection(list1->next, list2->next).****If (list1->data < list2->data)**: The head node list1 will never be part of the intersection because data stored in all the nodes in the second linked list would be greater than the list1->data (hint: both lists are sorted!). Now, the problem gets reduced to find the intersection of the remaining sizes**m - 1**and**n**. So our function call for smaller sub-problem is**listIntersection(list1->next, list2).****If (list1->data > list2->data**): The head node list2 will never be part of the intersection because data stored in all the nodes in the first linked list will be greater than the list2->data. Now, the problem gets reduced to find the intersection of the remaining list of size**m**and**n - 1**. So our function call for smaller sub-problem is**listIntersection(list1, list2->next).**

**Base case:** During the recursion, if any one of the lists reaches its end node i.e. if (list1 == NULL || list2 == NULL), we return NULL.

**Solution pseudocode**

```
ListNode listIntersection(ListNode list1, ListNode list2)
{
if (list1 == NULL || list2 == NULL)
return NULL
if (list1->data < list2->data)
return listIntersection(list1->next, list2)
else if (list1->data > list2->data)
return listIntersection(list1, list2->next)
else
{
ListNode temp
temp->data = list1->data
temp->next = listIntersection(list1->next, list2->next)
return temp
}
}
```

**Solution analysis**

At each step of the recursion, we are performing O(1) operation and input size decreases by 1 or 2. Suppose the length of both linked lists are m and n, then the total number of recursive calls would be m + n in the worst case. So the time complexity = O(m + n) * O(1) = O(m + n).

Here is the recurrence relation.

- T(m, n) = T(m, n - 1) + O(1), if (list1->data > list2->data)
- T(m, n) = T(m - 1, n) + O(1), if (list1->data < list2->data).
- T(m, n) = T(m - 1, n - 1) + O(1), if (list1->data == list2->data)

The space complexity depends on the size of the recursion call stack, which depends on the height of the recursion tree. Similarly, the height of the recursion tree depends on the value of m and n i.e. whichever value is larger, recursion tree depth depends on that value. So space complexity = O((max(m,n)). Think!

**Important note:** we recommend transforming the above pseudo-codes into a favorite programming language (C, C++, Java, Python, etc.) and verifying all the test cases. Enjoy programming!

- What would be the advantages of having doubly-linked lists instead of singly-linked lists for this problem?
- What would be the worst and best scenario of the above approaches?
- How can we solve this problem when linked lists are not sorted?
- Which of the above approach is more effcient in terms of memory or pointer operations? Compare the efficiency of the first three approaches.
- In the solution using local reference, can we build the output list by adding a new element to the front of the linked list?

- Union and Intersection of two Linked Lists
- Find the intersection point of two Linked Lists without finding the length
- Merge two sorted linked lists
- Sorted merge of two sorted doubly circular linked lists
- Insert value in a sorted way in a sorted doubly linked list

Please write in the message below if you find anything incorrect, or you want to share more insight. Enjoy learning, Enjoy algorithms!

Subscribe to get weekly content on data structure and algorithms, machine learning, system design and oops.