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