Find intersection of two linked lists using C++ program

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.

1. Sort both the linked list using merge sort. ( for detailed refer to: Merge sort for single linked lists)
2. 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

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