merge_list.c

#include<stdlib.h>
#include<stdio.h>
 
typedef struct node{
        int data;
        struct node *next;
} Node;
 
Node * merge_sort(Node *a, Node *b){
    Node *result = NULL;
    if(a ==  NULL)
        return b;
    else if(b == NULL)
        return a;

    /* For the first node, we would set the result to either a or b */
      if(a->data <= b->data){
         result = a;
        /* Result's next will point to smaller one in lists 
           starting at a->next  and b */
         result->next = merge_sort(a->next,b);
      }
      else {
        result = b;
       /*Result's next will point to smaller one in lists 
         starting at a and b->next */
        result->next = merge_sort(a,b->next);
      }
      return result;
}
/* Addition of a node to linked list */
void push(Node **head, int value){
        if(*head == NULL){
                (*head) = (Node *)malloc(sizeof(Node));
                (*head)->data = value;
                (*head)->next = NULL;
        }
        else{
                Node * temp = (Node *)malloc(sizeof(Node));
                if(temp){
                        temp->data = value;
                        temp->next = (*head);
                        *head = temp;
                }
        }
}
void print_list(Node * head){
    while(head){
        printf("%d->" , head->data );
        head = head->next;
    }

    printf("NULL");
    printf("\n");
}

 
/* Driver program to run above code */
int main(){
        Node * L1 = NULL;
        Node * L2 = NULL;
        Node * result = NULL;
        int carry = 0 ;
        /* creating list 1 */
        push(&L1,3);
        push(&L1,4);
        push(&L1,6);
        push(&L1,7);
        /* creating list 2 */
        push(&L2,8);
        push(&L2,1);
        push(&L2,10);
      
        L1 = merge_sort(L1,L2); 
        print_list(L1);
        
        return 0;
}