Intersection Point Of Two Linked Lists in 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.

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

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.