In this article, we will learn to find the intersection point of two linked lists using an optimized approach using C++. Linked lists are one of the most important associative data structures that are present out there.

We will start by going through the basic data structure of a linked list and then we will move to the problem statement. This question is a medium-level interview question that many top companies ask during the interviews. So without any further delay, let’s get started.

## What Are Linked Lists?

Linked lists are associative data structures that consist of nodes linked with each other. Every node has some data members and related functions. Below is the basic structure of the node of a linked list.

```
class Node
{
public:
// data members
int data;
Node *next;
// constructor
Node(int data): data(data), next(NULL) {}
};
```

## Problem Statement

*You are given two linked lists, find out the point of intersection of these linked lists.*

For example,

```
Linked list 1 is:
Head --> 5 --> 4 --> 3 --> 2 --> 1 --> Tail
Linked list 2 is:
Head --> 32 --> 132 --> 111 --> 8 --> 7 --> 3 --> 2 --> 1 --> Tail
The common portion between the two linkes lists is:
The linked list:
Head --> 3 --> 2 --> 1 --> Tail
Linked list 1 is:
Head --> 1 --> 5 --> 45 --> 3 --> 1 --> Tail
Linked list 2 is:
Head --> 1 --> 5 --> 45 --> 3 --> 1 --> Tail
The common portion between the two linkes lists is:
The linked list:
Head --> 1 --> 5 --> 45 --> 3 --> 1 --> Tail
```

## Concept of Intersection Point of Two Linked Lists

The approach is simple, rather than using the naive *O(N ^{2})* approach, we would go for a linear approach. Below are the complete details of the algorithm. Our algorithm would take two arguments

*head1*and

*head2*as input. Each of these arguments denotes a liked list.

- Find out the length of both the linked lists
- Initialize two pointer
*temp1*, and*temp2*to point to*head1*and*head2*respectively - Depending on the list that is longer, follow the steps given below
- Move the pointer of the longer list by the distance:
*(length_longer – length_shorter)*. - Now, you’ll notice that the pointers points to the lists of same size
- This makes things a lot easier for us
- Now, start iterating over the lists using a
*while*loop. Run the loop until the following condition is met*if(temp1->data == temp2->data)*

- Once the condition mentioned above is met, just break out of the
*while*and return either of the pointers, because we’ve found the intersection point.

- Move the pointer of the longer list by the distance:

## Intersection Point Of Two Linked Lists C++ Program

Let’s now write the C++ code for finding the intersection point of two linked lists.

```
#include <iostream>
using namespace std;
class Node
{
public:
int data;
Node *next;
Node(int data): data(data), next(NULL) {}
};
Node* insert_at_head(Node *head, int data)
{
// base case: if the list is empty
if(head == NULL)
{
head = new Node(data);
return head;
}
// otherwise, we proceed as follows
Node *temp = new Node(data);
temp->next = head;
head = temp;
return head;
}
Node* build_list()
{
cout << "Enter the elements of the linked list, press -1 to stop" << endl;
Node *head = NULL;
while(true)
{
int ele;
cin >> ele;
if(ele == -1)
break;
head = insert_at_head(head, ele);
}
return head;
}
int list_len(Node *head)
{
if(head == NULL)
{
return 0;
}
Node *temp = head;
int len = 0;
while(temp != NULL)
{
len++;
temp = temp->next;
}
return len;
}
Node* find_intersection_point(Node *head1, Node *head2)
{
cout << "The common portion between the two linkes lists is:" << endl;
// the approach is very simple
// we will take help of the concept of
// fast and slow pointers
// first we will find out the length of the linked lists
int len1 = list_len(head1);
int len2 = list_len(head2);
// once we have the length, we'll make two pointers
// point the each of the linked lists
Node *temp1 = head1;
Node *temp2 = head2;
int diff = abs(len1 - len2);
// based on the list that is longer, move the
// pointer pointing to that list by the distance
// diff = length_longer - length_shorter
if(len1 > len2)
{
while(diff--)
{
temp1 = temp1->next;
}
}
else
{
while(diff--)
{
temp2 = temp2->next;
}
}
// once this is over, both the pointers will have
// the same amount of data to move
// Now just run a while loop until the pointers
// points to the same address
while(true)
{
if(temp1->data == temp2->data)
{
break;
}
temp1 = temp1->next;
temp2 = temp2->next;
}
return temp1;
}
void print_list(Node *head)
{
cout << "The linked list is:" << endl << "Head --> ";
Node *temp = head;
while(temp != NULL)
{
cout << temp->data << " --> ";
temp = temp->next;
}
cout << "Tail" << endl;
}
int main()
{
Node *head1 = build_list();
print_list(head1);
Node *head2 = build_list();
print_list(head2);
Node *common = find_intersection_point(head1, head2);
print_list(common);
return 0;
};
```

## Output

## Conclusion

In this article, we learned to find the common portion of two liked lists using a *O(N)* approach, here *N* denotes the length of the longer linked list. We started by discussing linked lists, and problem statement and eventually developed the algorithm and test it. That’s all for today, thanks for reading.

## Further Readings

To learn more about linked lists, you can visit the following articles.

https://www.journaldev.com/55647/linked-lists-cpp

https://www.journaldev.com/61310/sort-linked-lists-cpp