Intersection of Two Sorted Linked Lists

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

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

Let’s understand the problem

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!

Discussed solution approaches

•  Two pointers approach using head and tail pointers
•  Two pointers approach using dummy node
• Recursive version of the iterative approach

Two pointers approach using head and tail pointers

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 and other linked list is 1->7->12->15->17, 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.

At any intermediate 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): 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.
• If(x->data < y->data): 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.

• intersecHead will 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 code C++

struct ListNode 
{
    int data;
    ListNode* next;
    ListNode(int val)
    {
        data = val;
        next = NULL;
    }
};

ListNode* listIntersection(ListNode* list1, ListNode* list2) 
{
    ListNode* intersecHead = NULL;
    ListNode* intersecTail = NULL;
    while (list1 != NULL && list2 != NULL) 
    {
        if (list1->data == list2->data) 
        {
            if (intersecHead == 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 code Python

class ListNode:
    def __init__(self, val):
        self.data = val
        self.next = None

def listIntersection(list1, list2):
    intersec_head = None
    intersec_tail = None
    while list1 is not None and list2 is not None:
        if list1.data == list2.data:
            if intersec_head is None:
                intersec_head = ListNode(list1.data)
                intersec_tail = intersec_head
            else:
                intersec_tail.next = ListNode(list1.data)
                intersec_tail = intersec_tail.next
            list1 = list1.next
            list2 = list2.next
        elif list1.data < list2.data:
            list1 = list1.next
        else:
            list2 = list2.next
    return intersec_head

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.

Two pointers approach using dummy node

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!

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 code C++

ListNode* listIntersection(ListNode* list1, ListNode* list2) 
{
    ListNode* dummy = new ListNode(0);
    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 code Python

def listIntersection(list1, list2):
    dummy = ListNode(0)
    intersec_tail = dummy
    while list1 is not None and list2 is not None:
        if list1.data == list2.data:
            intersec_tail.next = ListNode(list1.data)
            intersec_tail = intersec_tail.next
            list1 = list1.next
            list2 = list2.next
        elif 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).

Using recursive approach

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 code C++

// Function to find the intersection of two sorted singly-linked lists
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 = new ListNode(list1->data);
        temp->next = listIntersection(list1->next, list2->next);
        return temp;
    }
}

Solution code Python

def listIntersection(list1, list2):
    if list1 is None or list2 is None:
        return None

    if list1.data < list2.data:
        return listIntersection(list1.next, list2)
        
    elif list1.data > list2.data:
        return listIntersection(list1, list2.next)
        
    else:
        temp = ListNode(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 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!

Critical ideas to think!

• 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 efficient 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?

Similar coding questions to practice

• 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!