Intersection Of 2 Link Lists

Lecture 140:- Intersection Of 2 Link Lists

To find the intersection point of two singly linked lists, you can use the following approach:

1. Traverse both linked lists and find their lengths.
2. Calculate the difference in lengths between the two linked lists.
3. Move the pointer of the longer list by the difference calculated in step 2, so that both lists are of equal length from that point.
4. Traverse both lists simultaneously, comparing nodes. The first common node encountered is the intersection point.

Here's a C++ implementation of this approach:

cppCopy code

#include <iostream> class Node { public: int data; Node* next; Node(int value) : data(value), next(nullptr) {} }; int length(Node* head) { int len = 0; while (head) { len++; head = head->next; } return len; } Node* findIntersection(Node* head1, Node* head2) { int len1 = length(head1); int len2 = length(head2); int diff = std::abs(len1 - len2); // Move the pointer of the longer list by the difference if (len1 > len2) { while (diff--) { head1 = head1->next; } } else { while (diff--) { head2 = head2->next; } } // Traverse both lists simultaneously to find the intersection while (head1 && head2) { if (head1 == head2) { return head1; // Intersection point found } head1 = head1->next; head2 = head2->next; } return nullptr; // No intersection } int main() { Node* list1 = new Node(1); list1->next = new Node(2); list1->next->next = new Node(3); Node* commonNode = new Node(4); list1->next->next->next = commonNode; Node* list2 = new Node(7); list2->next = new Node(8); list2->next->next = commonNode; Node* intersection = findIntersection(list1, list2); if (intersection) { std::cout << "Intersection Point: " << intersection->data << std::endl; } else { std::cout << "No Intersection Point" << std::endl; } return 0; }

In this example, two linked lists are created, and a common node is introduced to represent the intersection point. The findIntersection function calculates the intersection point using the approach described earlier.

Make sure to handle cases where there is no intersection (i.e., one list doesn't intersect with the other).