Merge two linked list into a single list - DS TUTORIAL

demonstrate the merging of two link list into one single.

Description:

This example demonstrate how to merge two lists into a single list. Here you find mainly three function. The insertnode function makes node and insert data into it, printlist function prints all the data and the mergelist funtion merge the two lists into a single list.

Code:

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

Output: