Find Intersection Of Two Nodes In A Linked List

Let's start by understanding the problem statement of this task.

You are given two linked lists, your job is to find the node where the two linked lists intersect.

Hint:

The intersection of two linked lists means that the first node common to both the linked lists after which both the linked lists have all the nodes common and not that only the common node exists. For solving this type of problems we may think of either using an array data structure or the hashing technique, in using the array data structure approach we will require extra space which will be due to creation of two different arrays rest the time complexity will be O(n) as there are no nested loops used for this approach.

Quick Think:

For the array data structure approach discussed here, we will create two different arrays for storing the data of both the linked lists in it, and also we need to keep the following things in mind before proceeding:-

1. We need to first count the number of nodes in each linked list.
2. Declare two arrays to store the data value of the linked lists separately, with the size of the two arrays being the total number of nodes in each linked list.
3. Find the difference of the number of nodes in each linked list, and set the index of the array for finding the common node to the difference between the lengths of the two linked lists.
4. The data value insertion of the two nodes of linked lists should be from the back side of the array as we are using the method for pushing the nodes into the linked list for the beginning, the programmers can modify this function according to their logic.

Algorithm:

Step1: Push the nodes of the linked lists into the linked list (Here i have used push from the beginning method).

Step2: Create a function to count the total number of nodes in each linked lists with arguments as the head of the linked list and return its count to the main function.

Step3: Create the function with arguments as the head node of the first linked list, the head node of the second linked list, the count of the number of nodes of the first linked list and the count of the total number of nodes of the second linked list to store the data value of the nodes in two different arrays of size as the total number of nodes of the two linked lists, store the data values of the nodes and if the size of linked list 1 is greater than the size of the linked list 2 then calculate the difference as number of nodes in linked list 1 - number nodes in linked list 2 else the difference will be as different as number of nodes in linked list 2 - number nodes in linked list 1.

Step4: Now create a function to find the intersection node of the two linked lists with arguments as the array with larger length of the nodes, the second array and the difference of the length of the two linked lists and the total size of the array of larger length, here increment the index of the larger array to the difference found in the step 3 and keep comparing the data node of the two linked lists if the common node is found then print the data of the linked list.

Implementation Of The Above Algorithm:

Now let's see the implementation of the above algorithm,

#include <bits/stdc++.h>
using namespace std;
struct node
{
	int data;
	struct node * next;
};

/*Function to push the nodes into the linked list form the beginning. */
void push(struct node **head_ref, int data)
{
	struct node * node;
	node = (struct node *) malloc(sizeof(struct node));
	node->data = data;
	node->next = (*head_ref);
	(*head_ref) = node;
}

/*Function to count the total number of nodes in each linked list. */
int countnode(struct node *head)
{
	int count = 0;
	while (head != NULL)
	{
		count++;
		head = head->next;
	}

	return count;
}

/*Function to find the common node in both the linked lists. */
void findnodeintersection(int diff, int store1[], int store2[], int key)
{
	int i = diff;
	int j = 0;
	while (i < key)
	{
		if (store1[i] == store2[j])
		{
			cout << "The intersection node is = " << store1[i] << " ";
			break;
		}

		i++;
		j++;
	}
}

/*Function to store the data value of the linked lsit into the arrays. */
void findintersection(struct node *head1, struct node *head2, int count1, int count2)
{
	int i, diff;
	struct node *temp1 = head1;
	struct node *temp2 = head2;
	int store1[count1];
	int store2[count2];
	/*Storing the data value of the first linked list into store1 array. */
	for (i = count1 - 1; i >= 0; i--)
	{
		store1[i] = temp1->data;
		temp1 = temp1->next;
	}

	/*Storing the data value of the second linked list into store2 array. */
	for (i = count2 - 1; i >= 0; i--)
	{
		store2[i] = temp2->data;
		temp2 = temp2->next;
	}

	/*Comparing the lenght of both the arrays where count1 is greater then or equal to count2. */
	if (count1 >= count2)
	{
		diff = count1 - count2;
		findnodeintersection(diff, store1, store2, count1);
	}

	/*Comparing the lenght of both the arrays where count2 is greater then or equal to count1. */
	else if (count1 < count2)
	{
		diff = count2 - count1;
		findnodeintersection(diff, store2, store1, count2);
	}
}

/*Driver function to check te above algorithm. */
int main()
{
	struct node *head1 = NULL;
	struct node *head2 = NULL;
	push(&head2, 3);
	push(&head2, 6);
	push(&head2, 9);
	push(&head2, 15);
	push(&head2, 30);
	push(&head1, 10);
	push(&head1, 15);
	push(&head1, 30);
	int count1 = countnode(head1);
	int count2 = countnode(head2);
	findintersection(head1, head2, count1, count2);
	return 0;
}

The time Complexity of the above algorithm is O(n).

The output of the above algorithm is: The intersection node is = 15.

Explanation Of The Above Algorithm:

Let us take the example of the above two linked lists for the above algorithm understanding as shown in the figure above.

Now follow the following steps to reach the solution.

• Store the data values of the nodes in two different arrays, as shown in the diagram above.
• Now the total number of nodes in linked list 1 is “five” and the total number of nodes in linked list 2 is “three” now, we will find the difference in the number of nodes in the linked list so in this case, the difference will be “two”.

• Now start traversing the array “List1” from index “two” and keep comparing the data values stored in the two arrays, and we see that the value at “third” index of the list1 array matches with the “second” index of the list2 array and hence it is the intersection of the nodes in the two linked lists as shown in the diagram above.