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 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->20->27->NULL

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

Example 2

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

Output: NULL

Explanation: No nodes are common to both linked lists.

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

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 would be clear: common nodes will be present in the same increasing order in both linked lists. For example: if one linked list is 2->4->7->9->12->16->17->NULL and other linked list is 1->7->12->15->17->19->NULL, then the order of common nodes will be same i.e. (7, 12, 17).

The strategy here is to use the sorted order property, move forward in both lists, and build the output list. We move forward by comparing values one by one, and when the current nodes in both lists are the same, we add that node to the output list. Otherwise, whichever node value is smaller, we move forward in that list to search for the next value of the intersection. Think! 

Here is a detailed visualization of the steps. Suppose we are at a node x in list1 and y in list2 at any general point.

  • If(x->data == y->data): then both nodes are common, and we can 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): then the node with value y will not be present in list1. In other words, it will never be part of the output because the value of nodes present after x in list1 will be already greater than y. So, we need to move forward in list2 to search node x. Think!
  • If(x->data < y->data): then the node with value x will not be present in list2. In other words, it will never be part of the output because the value of nodes present after y in list2 is already greater than x. So we need to move forward in list1 to search node with the value y. Think!

Solution steps

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

  • We initialize two list pointers head and tail, with NULL to build the output list. Here we create the output incrementally, where the head pointer will track the first node, which we return as output, and the tail track the last node of the output list.
  • Now we run a loop till we reach the end of any one of the linked lists i.e. while (list1 != null && list2 != null). Why? Think! We move forward by comparing the first nodes in both lists, and whenever we find the first common node, we update it with the head node and tail node. After this, we find other common nodes based on the comparison and add them at the end of the tail node.
  • If (list1->data == list2->data), then we create a new list node equal to the value of any one of the node data, add it to the output by inserting it after the tail, and increment both list1 and list2 pointers to the next node in their corresponding linked list. Special note: when it is the first common node, we also update the head pointer with that node.
  • if (list1->data < list2->data), then we move the list1 pointer to the next node.
  • if (list1->data > list2->data), then we move the list2 pointer to the next node.
  • By the end of the loop, we return the head pointer of the output list.

Solution Pseudocode

ListNode listIntersection(ListNode list1, ListNode list2)
{
    ListNode head = null, tail = null
    while (list1 != null && list2 != null)
    {
        if (list1->data == list2->data)
        {
            if (head == null)
            {
                head = new ListNode(list1->data)
                tail = head
            }    
            else
            {
                tail->next = new ListNode(list1->data)
                tail = tail->next
            }    
            
            list1 = list1->next
            list2 = list2->next
        }

        else if (list1->data < list2->data)
            list1 = list1->next
        else
            list2 = list2->next
    }
    return head
}

Time and space complexity analysis

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

Another implementation using dummy node

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 a pointer tail which always points to the last node in the output list, so appending new nodes is easy at the end. The dummy node gives the tail something to point to initially when the output list is empty! Think!

Solution Steps

  • We create a list node dummy which points to the start of the output list. We also initialize a pointer tail with the dummy node, which points to the last node in the output list.
  • Now we traverse through 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 output list using the tail pointer.
  • Other operations inside the loop will remain the same as the above approach.
  • By the end of the loop, we return the head node i.e. next node of the dummy node as an output.

Solution Pseudocode

ListNode listIntersection(ListNode list1, ListNode list2)
{
    
    ListNode dummy = new ListNode()
    ListNode tail = dummy
    while (list1 != null && list2 != null)
    {
        if (list1->data == list2->data)
        {   
            tail->next = new ListNode(list1->data)
            tail = tail->next
            list1 = list1->next
            list2 = list2->next
        }

        else if (list1->data < list2->data)
            list1 = list1->next
        else
            list2 = list2->next
    }
    return dummy->next
}

Time and space complexity analysis

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

Implementation using local reference and helper function

This solution is also similar to the above approach, but it avoids using a dummy node. Instead, it maintains a linked list 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). Here function insertAtEnd() adds a new node at the end, and the new node becomes the last node in the list.
  • Then we update the lastNodeRef with the new last node of the output list.

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

Solution Pseudocode

ListNode listIntersection(ListNode list1, ListNode list2)
{
    
    ListNode output = NULL
    ListNode* lastNodeRef = &output
    
    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 output
}

void insertAtEnd(int data, ListNode *lastNode)
{
    ListNode newNode
    newNode->data = data
    (*lastNode)->next = newNode
}

Time and space complexity analysis

As we are using the loop idea similar to the above approach, where the time complexity of the insertAtEnd operation 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 1: Using a recursive approach

Solution Idea and Steps

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

Suppose we have two sorted linked lists of size m and n are given (with head nodes list1 and list2), and we need to return the linked list of nodes that are common in both input lists. So the idea is to identify common nodes, add them in the form of a linked list, and return the head pointer. Suppose our initial function call is listIntersection(list1, list2).

There will be three scenarios to build the recursive solution:

  • If (list1->data = list2->data): then the head nodes are common to both lists, and we can 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 of smaller sub-problem is listIntersection(list1->next, list2->next).
  • If (list1->data < list2->data): then the head node list1 will never be part of the intersection because data stored in all the nodes in list2 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 of smaller sub-problem is listIntersection(list1->next, list2).
  • If (list1->data > list2->data): then the head node list2 will never be part of the intersection because data stored in all the nodes in list1 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 of smaller sub-problem is listIntersection(list1, list2->next).

Base case: when during the recursion, 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
    }    
}

Time and space complexity analysis

Suppose the length of both linked lists are m and n. Here is the recurrence relation:

  • T(m, n) = T(m, n - 1) + O(1) if the head node of the list1 > the head node of the list2.
  • T(m, n) = T(m - 1, n) + O(1) if the head node of the list1 < the head node of the list2.
  • T(m, n) = T(m - 1, n - 1) + O(1) if the head node of the list1 = the head node of the list2.

The basic analysis would be simple: at each step of the recursion, we decrease the input size by 1 or 2 and perform an O(1) operation at each step. So total number of recursive calls would be O(m + n) and time complexity = O(m + n) * O(1) = O(m + n).

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!

Note: we highly recommend visualizing the analysis by drawing the recursion tree.

Critical ideas to think!

  • What would be the advantages of having doubly-linked lists instead of singly-linked lists for this problem?
  • What are the differences between pointer and reference?
  • 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

Enjoy coding, Enjoy learning, Enjoy algorithms!

We welcome your comments

Subscribe Our Newsletter

Get well-designed application and interview centirc content on ds-algorithms, machine learning, system design and oops. Content will be delivered weekly.