Home »
C++ programs
Find intersection of two linked lists using C++ program
In this article, we are going to see how to find intersection of two linked lists efficiently using merge sort?
Submitted by Radib Kar, on December 28, 2018
Problem statement: Write a C++ program to find the intersection of two single linked lists.
Example:
Let the first linked list be:
6->5->2->9->NULL
Let the second linked list to be:
2->7->NULL
So there intersection is:
2->NULL
Solution
Brute force approach:
One technique can be to traverse all the nodes of a linked list and check whether the traversed node is in the other linked list or not. Such an approach takes O(m*n) times complexity. m, n=length of linked lists.
Efficient approach:
Efficient approach use to use merge sort.
- Sort both the linked list using merge sort. ( for detailed refer to: Merge sort for single linked lists)
- Scan each linked list and build intersection according to following:
IF (list1->data < list2->data)
No intersection found
Traverse list1 by one step( list1=list1->next)
ELSE IF(list1->data ==list2->data)
Createnode(list1->data) && append node to the intersection list
Traverse list1 by one step( list1=list1->next)
Traverse list2 by one step( list2=list2->next)
ELSE//list1->data >list2->data
No intersection found
Traverse list2 by one step( list2=list2->next)
END IF-ELSE
- Display the intersection list
C++ implementation to find intersection of two linked lists
#include<bits/stdc++.h>
using namespace std;
class node{
public:
int data; // data field
struct node *next;
};
void display(class node* head){
node* current=head; // current node set to head
//traverse until current node isn't NULL
while(current!=NULL){
printf("%d ",current->data);
current=current->next; // go to next node
}
}
node* creatnode(int d){
node* temp=(node*)malloc(sizeof(node));
temp->data=d;
temp->next=NULL;
return temp;
}
//merging two sorted list
node* mergeList(node* split1,node* split2){
node* newhead=NULL;
//base cases
if(split1==NULL)
return split2;
if(split2==NULL)
return split1;
if(split1->data<=split2->data){
newhead=split1;
newhead->next=mergeList(split1->next,split2);
}
else{
newhead=split2;
newhead->next=mergeList(split1,split2->next);
}
return newhead;
}
//split list for merge sort
void splitList(node* head,node** split1,node** split2){
node* slow=head;
node* fast=head->next;
while(fast!=NULL){
fast=fast->next;
if(fast!=NULL){
slow=slow->next;
fast=fast->next;
}
}
*split1=head;
*split2=slow->next;
//spliting
slow->next=NULL;
}
//merge sort
void mergeSort(node** refToHead){
node* head=*refToHead;
node* split1,*split2;
//base case
if(head==NULL || head->next==NULL){
return;
}
//split the list in two halves
splitList(head,&split1,&split2);
//recursively sort the two halves
mergeSort(&split1);
mergeSort(&split2);
*refToHead=mergeList(split1,split2);
return;
}
node* findIntersection(node* head1, node* head2){
//base case
if(head1==NULL && head2==NULL)
return NULL;
node* head4=NULL,*temp;
//for inserting the first common node
while( head1!=NULL && head2!=NULL && head4==NULL){
if(head1->data<head2->data){
head1=head1->next;
}
//intersection nodes(intersection)
else if(head1->data==head2->data){
head4=creatnode(head1->data);
temp=head4;
head1=head1->next;
head2=head2->next;
}
else{
head2=head2->next;
}
}
//for other common nodes(intersection)
while( head1!=NULL && head2!=NULL){
if(head1->data<head2->data){
head1=head1->next;
}
//intersection nodes
else if(head1->data==head2->data){
temp->next=creatnode(head1->data);
temp=temp->next;
head1=head1->next;
head2=head2->next;
}
else{
head2=head2->next;
}
}
return head4;
}
int main(){
printf("creating the linked list by inserting new nodes at the end\n");
printf("enter 0 to stop building the list, else enter any integer\n");
int k;
node* curr,*temp;
cout<<"enter list1...\n";
scanf("%d",&k);
node* head1=creatnode(k); //buliding list, first node
scanf("%d",&k);
temp=head1;
///////////////////inserting at the end//////////////////////
while(k){
curr=creatnode(k);
temp->next=curr;//appending each node
temp=temp->next;
scanf("%d",&k);
}
cout<<"displaying list1...\n";
display(head1); // displaying the list
cout<<"\nenter list2...\n";
scanf("%d",&k);
node* head2=creatnode(k); //buliding list, first node
scanf("%d",&k);
temp=head2;
///////////////////inserting at the end//////////////////////
while(k){
curr=creatnode(k);
temp->next=curr;//appending each node
temp=temp->next;
scanf("%d",&k);
}
cout<<"displaying list1...\n";
display(head2);
//sort both the lists
mergeSort(&head1);
mergeSort(&head2);
cout<<"\ndisplaying their intersection...\n";
node* head4=findIntersection(head1,head2);
if(head4)
display(head4);
else
cout<<"No intersection found\n";
return 0;
}
Output
First run:
creating the linked list by inserting new nodes at the end
enter 0 to stop building the list, else enter any integer
enter list1...
6 5 2 9 0
displaying list1...
6 5 2 9
enter list2...
2 7 0
displaying list1...
2 7
displaying their intersection...
2
Second run:
creating the linked list by inserting new nodes at the end
enter 0 to stop building the list, else enter any integer
enter list1...
6 7 8 0
displaying list1...
6 7 8
enter list2...
1 5 2 0
displaying list1...
1 5 2
displaying their intersection...
No intersection found
Example with explanation:
First linked list: 6->5->2->9->NULL
Second linked list: 2->7->NULL
After applying merge sort:
First linked list: 2->5->6->9->NULL
Second linked list: 2->7->NULL
------------------------------------------------------
//for better understanding nodes are represented
//only by respective values
head1=2
head2=2
FindIntersection(2,2):
0th iteration
head1!=NULL && head2!=NULL
head1->data==head2->data //=2
thus head4(head of intersection list) =2
temp=head4=2
intersection list up to now:
2->NULL
head1=2->next=5;
head2=2->next=7;
1st iteration
head1!=NULL && head2!=NULL
head1->data<head2->data //5<7
thushead1=5->next=6;
temp=same as before
intersection list up to now:
2->NULL
head2=same as before;
2nd iteration
head1!=NULL && head2!=NULL
thushead1=6->next=9;
temp=same as before
intersection list up to now:
2->NULL
head2=same as before;
3rd iteration
head1!=NULL && head2!=NULL
head1->data>head2->data //9>7
thushead2=7->next=NULL;
temp=same as before
intersection list up to now:
2->NULL
Head1=same as before;
4th iteration
Head2=NULL
So, iteration stops & intersection list is build:
2->NULL