Quick actions

cmd+k|ctrl+k

Navigation

Languages

Intersection Point of two Linked Lists

Snippet info

Language

Cpp

Visibility

public

Author

preeti.gaur1790

Created

2022-05-28T11:12:24.692376Z

Updated

2022-05-31T05:35:04.411741Z

#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;
}
INFO