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

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

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;

}