Intersection_Point_of_Y_shaped_LinkedList.cpp

/*
Intersection Point of Y shaped LinkedList

@author: Rishikeshrajrxl
@created: 20/08/2020

***** Demo of the Program ******
ENTER THE LIST 1 : 10 -> 3 -> 7 -> 40 -> 15 -> 6
ENTER THE LIST 2 : 11 ->12 -> 20 

ENTER THE POSTION FOR INTERSECTION  w.r.t BIGGER LIST (i.e LIST 1): 5
DISPLAY THE LIST AFTER INTERSECTION : LIST 1:  10 ->3 ->7 ->40 ->15 ->6
                                      LIST 2:  11 ->12 ->20 ->15 ->6                 //as we can see List 2 is linked with List 1 at position 
INTERSECTION POINT IS : 5                                      
*/

#include <bits/stdc++.h> 
using namespace std;

class Node
{ 
     public:
     int data;
     Node*next1,*next2;
};
Node*head1=NULL,*head2=NULL;       //pointers to the Node
Node*temp1,*temp2,*ptr;

void Insert_1();                // function declaration
void Insert_2();
void Display_All();
void Intersect();
int Find_Intersection();
int ele;

int main()                  //  Main() function begins 
{
    int ch;
   do{
       cout<<"\n \n\n \t\t PROGRAM TO FIND INTERSECTION POINT"<<endl;
       cout<<"\t********************************************************************"<<endl;
       cout<<"\t 1) INSERT IN LIST 1 \t \t 2) INSERT IN LIST 2"<<endl;
       cout<<"\t 3) DISPLAY ALL LIST \t \t 4) INTERSECT LISTS AT SPECIFIC POSITION"<<endl;
       cout<<"\t 5) EXIT \t \t\t 6) FIND THE INTERSECTION POINT "<<endl;
       cout<<"ENTER YOUR CHOISE :";
       cin>>ch;
       switch(ch)
       {
           case 1:
           Insert_1();              //inserting values in List 1
           break;
           
           case 2:
           Insert_2();              //inserting values in List 2
           break;
           
           case 3:
           Display_All();           //returns the list
           break;
           
           case 4:
           Intersect();             //this function is used to intersect both list as per user's choise
           break;
           
           case 6:
           cout<<"Point Of Intersection : "<<Find_Intersection();       // returns the point of intersection  
           break;
           
           case 5:
           exit(0);
           break;
           
           default:
           cout<<"Invalid Input"<<endl;     
       };
   }while(1);
   return 0;
}                                //  End of Main() function
//-----------------------------------------------------------------------------
void Insert_1()
{   
    ptr=new Node();
    cout<<"ENTER THE ELEMENT : ";
    cin>>ele;
    ptr->data=ele;
    ptr->next1=NULL;
    if(head1==NULL){
        head1=ptr;
    }
    else{
        temp1=head1;
        while(temp1->next1!=NULL){
            temp1=temp1->next1;
        }
        temp1->next1=ptr;
    }
    cout<<"Inserted succesfully"<<endl;
}
//----------------------------------------------------------------------------------
void Insert_2()
{
    ptr=new Node();
    cout<<"ENTER THE ELEMENT : ";
    cin>>ele;
    ptr->data=ele;
    ptr->next2=NULL;
    if(head2==NULL){
        head2=ptr;
    }
    else{
        temp2=head2;
        while(temp2->next2!=NULL){
            temp2=temp2->next2;
        }
        temp2->next2=ptr;
    }
    cout<<"Inserted succesfully"<<endl;
}
//------------------------------------------------------------------------------------
void Display_All()
{
    cout<<"LIST 1 : ";
    temp1=head1;  
     
    while(temp1!=NULL){
        cout<<temp1->data<<" ";
        temp1=temp1->next1;
    }
    cout<<"\nLIST 2 : ";
    temp2=head2;
     
    while(temp2!=NULL){
        cout<<temp2->data<<" ";
        temp2=temp2->next2;
    }
}
//--------------------------------------------------------------------------------------
void Intersect()
{
    int length1=0,length2=0;
    string list="";
    temp1=head1; temp2=head2;
    
    while(temp1!=NULL){
        length1++;
        temp1=temp1->next1;
    }
    while(temp2!=NULL){
       length2++;
       temp2=temp2->next2;
    }
    if(length1>length2){
        list="LIST 1";
    }else{
        list="LIST 2";
    }
    cout<<"***********************************************************************"<<endl;
    cout<<"Since "<<list<<" is bigger in length."<<endl;
    cout<<"Tell the position of node in "<<list<<" on which you want to intersect : "<<endl;
    cout<<"***********************************************************************"<<endl;
     
    int pos;
    cout<<"ENTER THE POSITION : ";
    cin>>pos;
    temp1=head1;temp2=head2;
    
    if(length1>length2){
        while(temp2->next2!=NULL){
            temp2=temp2->next2;
        }
        for(int i=0;i<pos-1;i++){
            temp1=temp1->next1;
        }
        while(temp1!=NULL){
            temp2->next2=temp1;
            temp1=temp1->next1;
            temp2=temp2->next2;
        }
        cout<<"Intersection Successfull"<<endl;
    }
    else{
        while(temp1->next1!=NULL){
            temp1=temp1->next1;
        }
        for(int i=0;i<pos-1;i++){
            temp2=temp2->next2;
        }
        while(temp2!=NULL){
            temp1->next1=temp2;
            temp1=temp1->next1;
            temp2=temp2->next2;
        }
        cout<<"Intersection Successfull"<<endl;
    }
}
//--------------------------------------------------------------------------------------
/*
        Till now we have just work on intersecting two Linked List 
        Now, the main aim of this program is in the next function to find the Intersection point.
        
        Approach to solve this problem :- 
        ------------------------------
        We will calculate the length of individual and will iterate the longer List till it's 
        difference and then we wil iterate both the list together checking the pointer of next node 
        is same or not.       
*///---------------------------------------------------------------------------------------
int Find_Intersection()
{
    int length1=0,length2=0;
    temp1=head1; temp2=head2;
    
    while(temp1!=NULL){
        length1++;
        temp1=temp1->next1;             //finding length of list
    }
    while(temp2!=NULL){
       length2++;
       temp2=temp2->next2;
    }
    int  diff=abs(length1-length2);     //difference of both Lists
    temp1=head1; temp2=head2;
    
    if(length1>length2){
        for(int i=0;i<diff;i++){
                temp1=temp1->next1;
        }
    }
    else{
         for(int i=0;i<diff;i++){
                temp2=temp2->next2;
        }
    }
    while(temp1!=NULL && temp2!=NULL){
        if(temp1==temp2)
        return temp1->data;
        
        temp1=temp1->next1;
        temp2=temp2->next2;
    }
    return -1;
}