MERGE THE TWO LINK LIST IN SORTED ORDER

Q.) GIVEN THE TWO SORTED LIST MERGE THEM INTO A SINGLE LINK LIST IN SORTED ORDER.


example-
list1={1,4,6,8,10}
list2={1,2,3,4}
output list={1,1,2,3,4,6,8,10}

SOLUTION--


#include<stdio.h>
#include<stdlib.h>
struct node
{
    int data;
    struct node *next;
}*head;
int main()
{
    struct node *head1,*head2,*temp1,*temp2,*temp,*head;
    int num1,num2,i,item;
    head1=NULL;
    head2=NULL;
    head=NULL;
    printf("\nenter the no. nodes in first list=");
    scanf("%d",&num1);
    printf("\nenter the elemnts of node one by one");
    for(i=0;i<num1;i++)
    {
        scanf("%d",&item);
        if(head1==NULL)
        {
            head1=malloc(sizeof(struct node));
            head1->data=item;
            temp1=head1;
        }
        else
        {
            temp1->next=malloc(sizeof(struct node));
            temp1->next->data=item;
            temp1=temp1->next;
        }
      //  printf("%d ",temp1->data);
    }
    temp1->next=NULL;
    printf("\nenter the no. of nodes in second list=");
    scanf("%d",&num2);
    printf("\nenter the elements of node one by one");
    for(i=0;i<num2;i++)
    {
        scanf("%d",&item);
        if(head2==NULL)
        {
            head2=malloc(sizeof(struct node));
            head2->data=item;
            temp2=head2;
        }
        else
        {
            temp2->next=malloc(sizeof(struct node));
            temp2->next->data=item;
            temp2=temp2->next;
        }
    //    printf("%d ",temp2->data);
    }
    temp2->next=NULL;
    temp1=head1;
    temp2=head2;
    int flag=0;
    //mergeing the two link list//
    printf("\nlist in sorted order\n");
    for(i=0;i<num1+num2;i++)
    {
        if(flag==1||temp1!=NULL&&temp1->data<temp2->data)
        {
            if(head==NULL)
            {
                head=malloc(sizeof(struct node));
                head->data=temp1->data;
                temp=head;
            }
            else
            {
                temp->next=malloc(sizeof(struct node));
                temp->next->data=temp1->data;
                temp=temp->next;
            }

            temp1=temp1->next;
        }
        else
        {
             if(head==NULL)
            {
                head=malloc(sizeof(struct node));
                head->data=temp2->data;
                temp=head;
            }
            else
            {
                temp->next=malloc(sizeof(struct node));
                temp->next->data=temp2->data;
                temp=temp->next;
            }
            temp2=temp2->next;
            if(temp2==NULL)
                flag=1;
        }
         printf("%d ",temp->data);
    }
    temp->next=NULL;
    temp=head;
    //printinting the merged link list//
    /*while(temp!=NULL)
    {
        printf("%d ",temp->data);
        temp=temp->next;
    }*/
    return 0;
}