Intersection Point of two Linked Lists
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879
#include <iostream>
using namespace std;
class Node {
public :
int data;
Node *next;
Node() {
data = 0;
next = NULL;
}
Node(int data) {
this->data = data;
this->next = NULL;
}
};
int getLength(Node *head) {
if(head == NULL) return 0;
Node *temp = head;
int count = 0;
while(temp!=NULL) {
count++;
temp = temp->next;
}
return count;
}
int getIntersectionPoint(Node *head1, Node *head2, int diffOfNodes) {
cout << "diffOfNodes : " << diffOfNodes << endl;
if (diffOfNodes > 0) {
Node *temp = head1;
for(int i = 0; i< diffOfNodes; i++) {
temp = temp->next;
}
head1 = temp;
}
Node *temp1 = head1;
Node *temp2 = head2;
while(temp1 != NULL && temp2!=NULL) {
if(temp1->data == temp2->data) {
return temp1->data;
}
temp1 = temp1->next;
temp2 = temp2->next;
}
return -1;
}
int getIntersectionPoint(Node *head1, Node *head2) {
int len1 = getLength(head1);
int len2 = getLength(head2);
if (len1 == 0 || len2 == 0) {
return -1;
} else if (len1 > len2) {
return getIntersectionPoint(head1, head2, (len1-len2));
} else {
return getIntersectionPoint(head2, head1, (len2-len1));
}
}
int main() {
//cout << "Hello World!";
Node *head1 = new Node(1);
head1->next = new Node(2);
head1->next->next = new Node(3);
Node *head2 = new Node(10);
head2->next = new Node(25);
head2->next->next = head1->next->next;
int intersectionPoint = getIntersectionPoint(head1, head2);
cout << "intersectionPoint : " << intersectionPoint;
return 0;
}
Cpp
INFO