Wednesday, 14 September 2016

Merge Two link List( 1: Normal Approach 2: Recursion Approach)


Merge Two link List( 1; Normal Approach 2: Recursion Approach)


Merge-Link-list
Merge-Link-list


#include <stdio.h>
#include<stdlib.h>

using namespace std;

// defining structure for the link list

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

/* functions*/

node * Merge_list(node *x, node*y);
void display(node *n);
node *create_list();


node *create_list(node *ptr, int item)
{
    node *temp ;
    if(ptr==NULL)
    {
        ;
        temp = (node*)malloc(sizeof(node));
        temp->data = item;
        temp->next = ptr;
        ptr = temp;


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

}

node *Merge_list(node *x, node*y)
{
    if(x==NULL)
        return y;
    if(y==NULL)
        return x;

    node *t = x;
    node *ptr = x;
    x= x->next;
    while(x!=NULL && y!=NULL)
    {
        t->next = y;
        y = y->next;
        t = t->next;
        t->next = x;
        x= x->next;
        t=t->next;

    }
    if(x!=NULL)
        t->next = x;
    else if(y!=NULL)
        t->next = y;
    else
        t->next = NULL;
    return ptr;
}


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

/*using recurison*/

node* sort_merge_list(node* a, node *b)
{

    if(a==NULL)
        return b;
    if(b==NULL)
        return b;
    node* res = NULL;

    if(a->data <=b->data)
    {
        res = a;
        res->next = sort_merge_list(a->next,b);
    }
    else
    {
        res =b;
        res->next = sort_merge_list(a, b->next);
    }

    return res;
}
int main()
{
    node* list1 = NULL;
    list1 =  create_list(list1, 1);
    for(int i=2;i<10/2;i++)
    create_list(list1, i);
    display(list1);
    cout<<endl;
    node* list2 = NULL;
    list2 =  create_list(list2, 5);
    for(int i=11;i<30/2;i++)
      create_list(list2, i);
    display(list2);
    node* Mergelist = sort_merge_list(list1, list2);
    cout<<endl;
    display(Mergelist);
    cout<<endl;
    return 0;
}

0 comments:

Post a comment