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

struct listNode{
	int data;
	struct listNode* next;
} typedef listNode;

/* Function to print nodes in a given linked list */
void printList(listNode *node){
  while(node != NULL){
  	printf("%d ", node->data);
   	node = node->next;
  }
  printf("\n");
}

void push(listNode **head, int data){
	listNode *temp = (listNode *)malloc(sizeof(listNode));
	temp->data = data;
	temp->next = *head;
	*head = temp;
}

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct listNode* mergeTwoLists(struct listNode* a, struct listNode* b) {
    struct listNode* result = NULL;  
   /* Base cases */  
   if (a == NULL)  
     return(b);  
   else if (b == NULL)  
     return(a);  
   /* Pick either a or b, and recur */  
   if (a->data <= b->data) {  
     result = a;  
     result->next = mergeTwoLists(a->next, b);  
   }else {  
     result = b;  
     result->next = mergeTwoLists(a, b->next);  
   }  
   return(result); 
}

/* Driver program to test above functions*/
int main(){
  /* Start with the empty list */
  listNode *a = NULL;
  listNode *b = NULL;
  
  /* Let us create a unsorted linked lists to test the functions
  Created lists shall be a: 2->3->20->5->10->15 */
  push(&a, 15);
  push(&a, 10);
  push(&a, 5); 

  push(&b, 20);
  push(&b, 3);
  push(&b, 2); 
  push(&b, 1); 

  printList(a);
  printList(b);           
  /* Sort the above created Linked List */
  listNode *result = mergeTwoLists(a, b);
  printf("Merged Linked List is: ");
  printList(result);           
  
  return 0;
}