# How to find the intersection point of two linked lists?

Problem

For the above image, program needs to output: 4 as the intersection point.

###### Naive Approach

Run two for loops: outer loop from 0 to head1.length() and inner loop from 0 to head2.length(). Match each node of list1 with each node of list2. If there’s a match return node->value.

Pseudocode

Solve (head1, head2)
3.    for i=0 to length1:
4.      for j=0 to length2:
5.        if (node1 == node2) then:
6.          return  node1->value
7.        node2 = node2->next
8.      node1 = node1->next
9.  return null

Time Complexity: O(M*N) [where, M and N be the length of two linked lists respectively]
Auxiliary Space: O(1)

###### Optimised Approach

Let length1 will be the length of list1 and length2 will be the length of list2. Now assuming length1 > length2. Traverse list1 from head (0) to the difference of the two lists’ length (d = length1 – length2). Now we could traverse both the lists simultaneously to meet the intersection point, since the extra nodes of list1 have already been traversed.

Pseudocode

Solve (head1, head2)
3.  d = length1 - length2
3.  if length1 < length2 then:
6.    d = length2 - length1
7.  for i=0 to d:
8.    node1 = node1-next
9.  while (node1 != node2):
10.   node1 = node1->next
11.   node2 = node2->next
12. return node1    

Time Complexity: O(M + N)
Auxiliary Space: O(1)

Code Implementation

//
//  main.cpp
//  Intersection Point
//
//  Created by Himanshu on 03/10/21.
//

#include <iostream>
using namespace std;

struct node {
int info = 0;
struct node *next;
};
typedef struct node Node;

node* newNode(int data)
{
node* Node = new node();
Node->info = data;
Node->next = NULL;

return(Node);
}

while (x != NULL) {
cout<<(x->info)<<" ";
x = x->next;
}
cout<<endl;
}

Node* insertNode (Node *head, Node* x) {
while (node->next != NULL) {
node = node->next;
}
x->next = NULL;
node->next = x;
}

Node* searchNode (Node *head, int k) {

while (x != NULL && x->info != k) {
x = x->next;
}

if (x != NULL && x->info == k) {
return x;
} else {
return NULL;
}
}

int len = 0;
while (node != NULL) {
len++;
node = node->next;
}
return len;
}

int diff = len1 - len2;

if (len1 < len2) {
diff = len2 - len1;
}

for (int i=0; i<diff; i++) {
node1 = node1->next;
}

while (node1 != node2) {
node1 = node1->next;
node2 = node2->next;
}

return node1;
}

int main() {

if (x) {
cout<<"Intersection point is: "<<(x->info)<<endl;
} else {
cout<<"No intersection point found"<<endl;
}

return 0;
}


Output

Linked List 1:
1 2 3 4 8
Intersection point is: 4