Intersection of two Sorted Linked lists

Given two sorted Linked lists then we need to get a new Linked list which is intersection of the two given Linked lists

Example

Algorithm

Time Complexity: O(m+n) where,

m = number of nodes in list 1
n = number of nodes in list 2

Step 1 : Create a function which takes the two linked lists as arguments and gives out a new linked list with the intersection of elements.

Step 2 : Create a NULL node, where we can append the common elements.

Step 3 : Stores last value entered, as intersection has only one instance of the value common between the 2 lists.

Step 4 : traverse the two lists until one is fully traversed or both are traversed.
a)     Compare the elements such that if element in list 1 is greater than element in list 2, traverse in list 2.
b)    Compare the elements such that if element in list 2 is greater than element in list 1, traverse in list 1.
c)    If both are equal, insert the element at the end of the list. Because, it should be in sorted form.
d)    While adding into the list, compare with last entered value such that element should not be added twice. If added update last entered value, such that next time

Step 5 : on the given two linked lists, call this function. It will give a pointer to head of new linked list where elements are intersection of the given two linked lists.

Algorithm working Example

C++ Program

#include <bits/stdc++.h>
using namespace std;

struct LL{
	int data;
	LL *next;	
};


void insertAtEnd(struct LL**head,int dataToBeInserted)
{
	
	struct LL*temp = *head;
	
	if(*head == NULL)
	{
		*head = new LL;
		(*head)->data = dataToBeInserted;
		(*head)->next = NULL;
	}
	
	else{
	
	while(temp->next!=NULL)
		temp=temp->next;
		
	temp->next=new LL;
	temp=temp->next;
	temp->data=dataToBeInserted;
	temp->next=NULL;
	}
	//O(number of nodes)
}

void intersection(struct LL *&finalList,struct LL **head1 , struct LL **head2)
{
	struct LL *temp1 = *head1 , *temp2 = *head2;
	int last_entered_value; //stores last value entered as intersection has only one instance of the value common between the 2 lists
	
	while(temp1 and temp2) //till one of the list or both lists are traversed
	{
		
		if(temp1->data < temp2->data)
			temp1 = temp1->next;
			
		else if(temp2->data < temp1->data)
			temp2 = temp2->next;
		
		else
		{
			if(last_entered_value != temp1->data)
				{
				insertAtEnd(&finalList,temp1->data);
				last_entered_value = temp1->data;
				}
			temp1 = temp1->next;
			temp2 = temp2->next;
		}
	}
	
	
}

void display(struct LL**head)
{
	struct LL*temp=*head;
	while(temp!=NULL)
		{
			if(temp->next!=NULL)
			cout<<temp->data<<" ->";
			else
			cout<<temp->data;
			
			temp=temp->next; //move to next node
		}
		//O(number of nodes)
	cout<<endl;
}


int main()
{
	
	struct LL *head1 = NULL; //initial list has no elements
	insertAtEnd(&head1,6);
	insertAtEnd(&head1,16);
	insertAtEnd(&head1,16);
	insertAtEnd(&head1,16);
	insertAtEnd(&head1,25);
	insertAtEnd(&head1,50);
	insertAtEnd(&head1,79);
	insertAtEnd(&head1,96);
	
	cout <<"First list is :-\n";
	display(&head1);
	
	struct LL *head2 = NULL;
	insertAtEnd(&head2,2);
	insertAtEnd(&head2,16);
	insertAtEnd(&head2,36);
	insertAtEnd(&head2,50); 
	insertAtEnd(&head2,50);
	insertAtEnd(&head2,50);
	insertAtEnd(&head2,60);
	insertAtEnd(&head2,79);
	insertAtEnd(&head2,96);
	insertAtEnd(&head2,96);
	insertAtEnd(&head2,123);
	
	cout <<"\nSecond list is :-\n";
	display(&head2);
	
	struct LL *finalList = NULL;

	intersection(finalList,&head1,&head2);
	
	cout <<"\nFinal list having intersection of the two lists is :-\n";
	display(&finalList);

	return 0;
}
Try It


Next > < Prev
Scroll to Top