# 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?
By Radib Kar Last updated : August 01, 2023

## Problem statement

Given two singly linked list, write a C++ program to find the intersection of two given singly linked list.

Consider the below example with sample input and output:

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

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

```#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->next = mergeList(split1->next, split2);
}
else {
newhead->next = mergeList(split1, split2->next);
}
}

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

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

//merge sort
{
node *split1, *split2;
//base case
if (head == NULL || head->next == NULL) {
return;
}
//split the list in two halves
//recursively sort the two halves
mergeSort(&split1);
mergeSort(&split2);

*refToHead = mergeList(split1, split2);

return;
}

{
//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) {
}
//intersection nodes(intersection)
}
else {
}
}

//for other common nodes(intersection)
while (head1 != NULL && head2 != NULL) {
}
//intersection nodes
temp = temp->next;

}
else {
}
}

}

// Main code
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";
display(head1); // displaying the list

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