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.

  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:
  3. 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
    
  4. 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




Comments and Discussions

Ad: Are you a blogger? Join our Blogging forum.



Languages: » C » C++ » C++ STL » Java » Data Structure » C#.Net » Android » Kotlin » SQL
Web Technologies: » PHP » Python » JavaScript » CSS » Ajax » Node.js » Web programming/HTML
Solved programs: » C » C++ » DS » Java » C#
Aptitude que. & ans.: » C » C++ » Java » DBMS
Interview que. & ans.: » C » Embedded C » Java » SEO » HR
CS Subjects: » CS Basics » O.S. » Networks » DBMS » Embedded Systems » Cloud Computing » Machine learning » CS Organizations » Linux » DOS
More: » Articles » Puzzles » News/Updates

© https://www.includehelp.com some rights reserved.