Q:

# Find intersection of two linked lists using C++ program

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```

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 complexitymn=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;
};

//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
```