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
  •  An implementation using dummy node
  •  An implementation using local references
  • 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->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.

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! 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).

Two pointers approach using local reference and helper function

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

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

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

Similar coding questions to practice

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

Share feedback with us

More blogs to explore

Our weekly newsletter

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

© 2022 Code Algorithms Pvt. Ltd.

All rights reserved.