Thursday, 15 September 2016

Find merge point of two linked list

Find-merge-point-of-two-linked-list
Find merge point of two linked list

Find merge point of two linked list






#include<iostream>
#include<stdio.h>
using namespace std;

typedef struct Node
{
    int data;
    struct Node *next;
}node;

int find_count(node *head);
int Get_insection_point(int , node*, node*);
int Get_insection_node(node*, node*);
void display(node* ptr);

int main()
{
   node* newNode;
   node* head1 =
            ( node*) malloc(sizeof( node));
  head1->data  = 10;

   node* head2 =
            ( node*) malloc(sizeof( node));
  head2->data  = 3;

  newNode = ( node*) malloc (sizeof( node));
  newNode->data = 6;
  head2->next = newNode;

  newNode = ( node*) malloc (sizeof( node));
  newNode->data = 9;
  head2->next->next = newNode;

  newNode = ( node*) malloc (sizeof( node));
  newNode->data = 15;
  head1->next = newNode;
  head2->next->next->next  = newNode;

  newNode = ( node*) malloc (sizeof( node));
  newNode->data = 30;
  head1->next->next= newNode;

  head1->next->next->next = NULL;



        cout<<"Elements in List 1 "<<endl<<endl;
        display(head1);
        cout<<endl;
        cout<<"Elements in List 2 "<<endl<<endl;
        display(head2);

        cout<<"\n\n Insection node is:- "<<Get_insection_node(head1,head2)<<endl<<endl;
        return 0;
}

void display(node* ptr)
{
    while(ptr!=NULL)
    {
        cout<<ptr->data<< " ";
        ptr=ptr->next;
    }
    cout<<endl<<endl;
}

node* create_list(node* head, int item)
{
    node* ptr = head;
    if(ptr ==NULL)
    {
        ptr = (node*)malloc(sizeof(node));
        ptr->data = item;
        ptr->next = NULL;
        head =ptr;
    }
    else
    {
        while(ptr->next!=NULL)
        {
            ptr= ptr->next;
        }
        ptr->next = (node*)malloc(sizeof(node));
        ptr= ptr->next;
        ptr->data = item;
        ptr->next = NULL;
    }
return ptr;
}

int find_count(node *head)
{
    int count1=0;
    while(head!=NULL)
    {
        count1++;
        head=head->next;
    }
    return count1;
}

int Get_insection_node(node* head1, node* head2)
{
    node * node1Ptr = head1;
    node* node2Ptr = head2;
    int d=0;
    int countC1 = find_count(node1Ptr);
    cout<<"no of elements in List 1 :-"<<countC1<<endl;
    int countC2 = find_count(node2Ptr);
    cout<<"no of elements in List 2 :-"<<countC2<<endl;
    if(countC1>countC2)
    {
        d = countC1-countC2;
        return Get_insection_point(d,node1Ptr,node2Ptr );
    }
    else
    {
        d= countC2-countC1;
        return Get_insection_point(d,node2Ptr,node1Ptr );
    }
}

int Get_insection_point(int d , node* head1, node* head2)
{
     node * node1Ptr = head1;
    node* node2Ptr = head2;

    for(int i=0;i<d;i++)
    {
        if(node1Ptr==NULL)
        {
            return -1;
        }
        node1Ptr = node1Ptr->next;
    }

    while(node1Ptr!=NULL && node2Ptr!=NULL)
    {

        if(node1Ptr->data == node2Ptr->data)
            return node1Ptr->data;
        node1Ptr = node1Ptr->next;
        node2Ptr = node2Ptr->next;
    }
    return -1;
}

0 comments:

Post a comment