Problem
Given the head pointers (head1 and head2) of two linked lists, find the intersection node of the two lists.
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) 1. node1 = head1, node2 = head2 2. length1 = head1.size(), length2 = head2.size() 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) 1. node1 = head1, node2 = head2 2. length1 = head1.size(), length2 = head2.size() 3. d = length1 - length2 3. if length1 < length2 then: 4. node1 = head2 5. node2 = head1 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);
}
void printLinkedList (Node* head) {
Node *x = head;
while (x != NULL) {
cout<<(x->info)<<" ";
x = x->next;
}
cout<<endl;
}
Node* insertNode (Node *head, Node* x) {
Node *node = head;
while (node->next != NULL) {
node = node->next;
}
x->next = NULL;
node->next = x;
return head;
}
Node* searchNode (Node *head, int k) {
Node* x = head;
while (x != NULL && x->info != k) {
x = x->next;
}
if (x != NULL && x->info == k) {
return x;
} else {
return NULL;
}
}
int findListLength (Node *head) {
int len = 0;
Node *node = head;
while (node != NULL) {
len++;
node = node->next;
}
return len;
}
Node* solve (Node *head1, Node *head2) {
Node *node1 = head1, *node2 = head2;
int len1 = findListLength(head1), len2 = findListLength(head2);
int diff = len1 - len2;
if (len1 < len2) {
node1 = head2;
node2 = head1;
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() {
Node *head1 = newNode(1);
Node *head2 = newNode(9);
head1 = insertNode (head1, newNode(2));
head1 = insertNode (head1, newNode(3));
head1 = insertNode (head1, newNode(4));
head1 = insertNode (head1, newNode(8));
head2 = insertNode (head2, newNode(5));
head2 = insertNode (head2, newNode(7));
Node *x = searchNode(head2, 7);
x->next = searchNode(head1, 4);
cout<<"Linked List 1:"<<endl;
printLinkedList(head1);
cout<<"Linked List 2:"<<endl;
printLinkedList(head2);
x = solve(head1, head2);
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 Linked List 2: 9 5 7 4 8 Intersection point is: 4
Here’s a working example: Intersection point of two linked lists