# include <stdio.h>
# include <stdlib.h>
struct node
{
int data;
struct node *link;
};
struct node *mergelist (struct node *, struct node *);
struct node *insertnode(struct node *p , int n)
{
	struct node *temp;
   if(p==NULL)
   {
      p=(struct node *)malloc(sizeof(struct node));
      if(p==NULL)
      {
      	printf("Error\n");
           exit(0);
      }
       p-> data = n;
       p-> link = NULL;
    }
    else
    {
      temp = p;
      while (temp-> link!= NULL)
     	 temp = temp-> link;
      temp-> link =  (struct node *)malloc(sizeof(struct node));
      if(temp -> link == NULL)
      {
      	printf("Error\n");
           exit(0);
      }
    temp = temp-> link;
      temp-> data = n;
      temp-> link = NULL;
     }
     return (p);
}
      

void printlist ( struct node *p  )
{
   printf("The data values in the list are\n");
   while (p!= NULL)
      {
      	printf("%d\t",p-> data);
         p = p-> link;
      }
}


void main()
{
		int n;
		int x;
		struct node *start1 = NULL ;
		struct node *start2 = NULL;
		struct node *start3 = NULL;
		printf("Enter the number of nodes for the first list \n");
		scanf("%d",&n);
		while ( n-- > 0 )
		{
			printf( "Enter the data for the first node\n");
			scanf("%d",&x);
			start1 = insertnode ( start1 ,x);
		}

		printlist ( start1 );
		printf("\nEnter the number of nodes for the second list \n");
		scanf("%d",&n);
		while ( n-- > 0 )
		{
			printf( "Enter the data for the second node\n");
			scanf("%d",&x);
			start2 = insertnode ( start2 ,x);
		}
		printlist ( start2 );
		start3 = mergelist(start1,start2);
		printf("\nThe merged list is\n");
		printlist ( start3);
}

struct node *mergelist (struct node *p, struct node *q)
  {
	 struct node *r=NULL,*temp;
		  if (p == NULL)
				 r =  q;
		  else
		  if(q == NULL)
				 r = p;
		  else
				{
					 if (p->data < q->data )
					 {
	r = p;
	temp = p;
	p = p->link;
	temp->link = NULL;
					}
				  else
					{
	r = q;
	temp =q;
	q =q->link;
	temp->link = NULL;
				  }
				 while((p!= NULL) &&  (q != NULL))
				 {
								if (p->data < q->data)
				  {
				  temp->link =p;
				  p = p->link;
				  temp =temp->link;
				  temp->link =NULL;
						  }
								 else
				{
				  temp->link =q;
				  q = q->link;
				  temp =temp->link;
				  temp->link =NULL;
						  }

	}
	if (p!= NULL)
			  temp->link = p;
	if (q != NULL)
				temp->link  = q;
		}
return( r) ;
}