# Intersection Point Of Two Linked Lists in C++

Filed Under: C++

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.

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
Head --> 32 --> 132 --> 111 --> 8 --> 7 --> 3 --> 2 --> 1 --> Tail
The common portion between the two linkes lists is:
Head --> 3 --> 2 --> 1 --> Tail

Head --> 1 --> 5 --> 45 --> 3 --> 1 --> Tail
Head --> 1 --> 5 --> 45 --> 3 --> 1 --> Tail
The common portion between the two linkes lists is:
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(N2) 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.

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

{
// base case: if the list is empty
{
}

// otherwise, we proceed as follows
Node *temp = new Node(data);

}

Node* build_list()
{
cout << "Enter the elements of the linked list, press -1 to stop" << endl;

while(true)
{
int ele;
cin >> ele;

if(ele == -1)
break;

}

}

{
{
return 0;
}

int len = 0;

while(temp != NULL)
{
len++;
temp = temp->next;
}

return len;
}

{
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
// once we have the length, we'll make two pointers
// point the each of the linked lists

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

{
cout << "The linked list is:" << endl << "Head --> ";

while(temp != NULL)
{
cout << temp->data << " --> ";
temp = temp->next;
}

cout << "Tail" << endl;
}

int main()
{

print_list(common);

return 0;
};
```

## 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.