How to find the intersection of two sorted linked list

A linked list is a common data structure made of one or more than one nodes. Each node contains a value and a pointer to the previous/next node forming the chain-like structure. These nodes are stored randomly in the system's memory, which improves its space complexity compared to the array.

Understanding the problem

We get two sorted linked lists, and we need to find the intersection of the given linked lists. Here, the intersection means the common nodes' value of both linked lists. We're not allowed to make any changes to the given linked lists. Therefore, we must make a new linked list and return the head of the new linked list having common elements of the given linked list. Let's visualize this problem:

Simple solution

Suppose we get two linked lists, and the basic approach is to use their head to traverse both lists. Now start comparing the linked lists, and while traversing, we check if both the elements of the lists are equal, then we add that node to our newly created resultant list.

This resultant list stores common elements of both linked lists. We use the tail pointer to add new nodes to the resultant list by pointing them to the last node. In our resultant intersection list, the values are allocated from the next node of the dummy—(dummy. link).

#include<iostream>
using namespace std;
class node {
public:
	int data;
	node* link;
};
node* add_node(node* ptr, int data) {
	
	node* temp = new node();
	temp->data = data;
	temp->link = NULL;
	node* end_node=ptr;
	if (end_node == NULL){
		end_node = temp;
  
  }
	else {
		while (end_node->link != NULL)
			end_node = end_node->link;
		end_node->link = temp;
	}
  return end_node;
}
void print_data(node* head) {
	if (head == NULL) {
		cout << "Linked List is empty" << endl;
		return;
	}
	node* temp_node = new node();
	temp_node=head;
	
	while (temp_node != NULL) {
		cout << temp_node->data << " ";
		temp_node = temp_node->link;
	}
}
node* intersection(node* a, node* b)
{
    
    node dummy; //temp node
    node* tail = &dummy;
    dummy.link = NULL;
    while (a != NULL && b != NULL) { //loop for traversing element
        if (a->data == b->data) { //finding common element
            tail=add_node((tail), a->data); //inserting it in new list
            tail = tail->link; //saving the address
            a = a->link;
            b = b->link;
        }
        else if (a->data < b->data) //finding smaller element
            a = a->link; //if a is smaller, traversing next node
        else
            b = b->link; //if a is larger, traversing next node
    }
    return (dummy.link);
}
int main(){
  node* list1=new node();
  node* list2=new node();
  node* list3=NULL;  
	list1 = NULL; list2=NULL;
  
  list1=add_node(list1,0);
  add_node(list1,2);
  add_node(list1,4);
  add_node(list1,6);
  cout << "Linked List 1: ";
  print_data(list1);
  
  list2=add_node(list2,4);
  add_node(list2,6);
  add_node(list2,7);
  cout << "\nLinked List 2: ";
  print_data(list2);
  
  list3=intersection(list1,list2);
  cout << "\nResultant: ";
  print_data(list3);
}

Explanation

Here's the step-by-step explanation of the code:

Lines 43–48: We define the intersection function in which we create the dummy node that temporarily stores the node's value.
Lines 50–55: We use the while loop to traverse both a and b linked lists. If we get any common node between them, we insert it into the dummy node.
Lines 57–62: We check whether the current element a is smaller than the current element b and move to the next node accordingly. Finally, we return the pointer—dummy.link.

Time Complexity: O(m+n), where m and n are the numbers of nodes in the first and second linked lists, respectively.

Space Complexity: O(min(m, n)), since the output list can store at most min(m, n) nodes.

Efficient solution

We think of recursion to do this efficiently. We use the recursive function that takes two nodes and returns the intersected node list will be used instead of the traditional method.

Comparing the first two items of each list is the most efficient strategy. In this case, we call the recursive function with the next node from both lists and return a node with the common node data. Otherwise, if they are not similar, we remove the smaller node from both lists and recursively call the recursive function for the second time.

//function for finding common nodes in a and b
node* intersection(node* a, node* b)
{
    if(a==NULL || b==NULL)
        return NULL;  //if any list is empty
    
    if (a->data < b->data)
        return intersection(a->link, b); //recursion using smaller element
    if (a->data > b->data)
        return intersection(a, b->link); //recursion
    
    node* temp = new node();
    temp->data = a->data;  //storing in temp node
    temp->link = intersection(a->link,b->link); //recursion
    return temp;
}
//driver code
int main(){
  node* list1=new node();
  node* list2=new node();
  node* list3=NULL;  
	list1 = NULL; list2=NULL;
  
  list1=add_node(list1,0);
  add_node(list1,2);
  add_node(list1,4);
  add_node(list1,6);
  cout << "Linked List 1: ";
  print_data(list1);
  
  list2=add_node(list2,4);
  add_node(list2,6);
  add_node(list2,7);
  cout << "\nLinked List 2: ";
  print_data(list2);
  
  list3=intersection(list1,list2);
  cout << "\nResultant: ";
  print_data(list3);
}

Explanation

Lines 2–5: We define the intersection function and it returns NULL if any of the lists is empty.
Lines 7–11: We find the current smaller element in both a and b and call recursively the intersection function using that smaller element.
Lines 13–16: We store the current value intemp and call the intersection function using recursion for the next element.

Time Complexity: O(m+n), where m and n are the numbers of nodes in the first and second linked lists, respectively.

Space Complexity: O(min(m, n)), since the output list can store at most min(m, n) nodes.

Free Resources