# 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;
};

//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){
//base cases
if(split1==NULL)
return split2;
if(split2==NULL)
return split1;

if(split1->data<=split2->data){
}
else{
}
}

//split list for merge sort

while(fast!=NULL){
fast=fast->next;
if(fast!=NULL){
slow=slow->next;
fast=fast->next;
}
}

*split2=slow->next;
//spliting
slow->next=NULL;
}

//merge sort
node* split1,*split2;
//base case
return;
}
//split the list in two halves
//recursively sort the two halves
mergeSort(&split1);
mergeSort(&split2);

return;
}

//base case
return NULL;

//for inserting the first common node
}
//intersection nodes(intersection)
}
else{
}
}

//for other common nodes(intersection)
}
//intersection nodes
temp=temp->next;

}
else{
}
}

}

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);

///////////////////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";
cout<<"\nenter list2...\n";
scanf("%d",&k);
node* head2=creatnode(k); //buliding list, first node
scanf("%d",&k);

///////////////////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";

//sort both the lists

cout<<"\ndisplaying their intersection...\n";

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

After applying merge sort:
------------------------------------------------------
//for better understanding nodes are represented
//only by respective values
FindIntersection(2,2):

0th iteration
intersection list up to now:
2->NULL

1st iteration
temp=same as before
intersection list up to now:
2->NULL

2nd iteration
temp=same as before
intersection list up to now:
2->NULL

3rd iteration
temp=same as before
intersection list up to now:
2->NULL

4th iteration
So, iteration stops & intersection list is build:
2->NULL
```

Preparation

What's New

Top Interview Coding Problems/Challenges!