Create two singly linked lists sort one after creation & one while creation.Merge these two lists into one list without creating a new node .

/* -------------------------------------------------------------------------------------------------

Program     : Create two singly linked lists sort one after creation & one while

                        creation.Merge these two lists into one list  without creating a new
                        node.

Created By : JABIR DAUD PATHAN

Branch        : COMPUTER ENGINEERING

-----------------------------------------------------------------------------------------------------*/

/*--------------------<<  Header File  >>--------------------*/

#include<stdio.h>

#include<conio.h>

#include<alloc.h>

/*-----<< Global Declaration of Structure and Functions  >>-------*/

typedef struct node

 {

  int data;

  struct node*next;

 }node;

node*create();

node*create_sort();

node *merge(node*head1,node*head2);

void display(node*head);

void sort(node*head);

node*head,*nwnode;

int ch,no,i,j; //Global Declaration of variables

/*------<< function defination for create linked list >>-----*/

node*create()

 {

  printf("\nEnter no. of nodes==>");

  scanf("%d",&no);

  printf("\n\nEnter values of nodes==>");

  head=(node*)malloc(sizeof(node));

  scanf("%d",&(head->data));

  head->next=NULL;

  nwnode=head;

  for(i=1;i<no;i++)

   {

    nwnode->next=(node*)malloc(sizeof(node));

    nwnode=nwnode->next;

    scanf("%d",&(nwnode->data));

    nwnode->next=NULL;

   }

   printf("\n\nCreated link list==>");

   return(head);

}

/*------<< function defination for display linked list >>-----*/

void display(node*head)

 {

  node*p;

  printf("\n\n\t\thead--->");

  for(p=head;p!=NULL;p=p->next)

   {

    printf("%d--->",(p->data));

   }

  printf("NULL");

 }

/*-------<< function defination for sort linked list >>-----*/

void sort(node*head)

 {

  int i,j,temp;

  node*p;

  printf("\n\nAfter sorting linked list==>");

  for(i=1;i<no;i++)

   {

    p=head;

    for(j=0;j<no-i;j++)

     {

      if(p->data>p->next->data)

       {

            temp=p->data;

            p->data=p->next->data;

            p->next->data=temp;

       }

      p=p->next;

     }

   }

 }

/*------<< function defination for create sorted linked list >>------*/

node*create_sort()

 {

  node *head=NULL,*p,*q;

  int x,i;

  printf("\nEnter no. of nodes==>");

  scanf("%d",&no);

  printf("\n\nEnter values of node==>");

  for(i=1;i<=no;i++)

   {

     scanf("%d",&x);

     p=(node*)malloc(sizeof(node));

     p->data=x;

     p->next=NULL;

     if(head==NULL || x<head->data)

      {

            p->next=head;

            head=p;

      }

     else

     {

      q=head;

      while(q->next !=NULL && x>q->next->data)

            q=q->next;

            p->next=q->next;

            q->next=p;

     }

   }

   printf("\n\nCreated link list==>");

   return(head);

 }

/*------<< function defination for merge two linked list >>-----*/

node *merge(node*head1,node*head2)

 {

  node *j,*p;

  j=NULL;

  while(head1!=NULL && head2!=NULL)

   {

    if(head1->data < head2->data)

     {

      if(j==NULL)

       {

            j=p=head1;

            head1=head1->next;

       }

      else

       {

                p->next=head1;

                head1=head1->next;

                p=p->next;

       }

     }

    else

     {

      if(j==NULL)

       {

            j=p=head2;

            head2=head2->next;

       }

      else

       {

            p->next=head2;

            head2=head2->next;

            p=p->next;

       }

     }

   }

 if(head1!=NULL)

  {

   if(j==NULL)

     j=head1;

   else

     p->next=head1;

  }

 if(head2!=NULL)

  {

   if(j==NULL)

     j=head2;

   else

     p->next=head2;

  }

  return(j);

 }

/*---------<<  Main Function Start  >>--------------*/

void main()

 {

  node*head1,*head2,*head3;

  clrscr();

  printf("\n\nCreate normal linked list==>\n");

  head1=create();

  display(head1);

  sort(head1);

  display(head1);

  printf("\n\n\nCreate normal linked list==>\n");

  head2=create_sort();

  display(head2);

  printf("\n\n\nAfter merging final list is==>");

  head3=merge(head1,head2);

  display(head3);

  getch();

}

/*---------<<  End Of Main Function  >>-----------*/

/*-----------------<< OUTPUT SCREEN  >>-------------------*/

Create normal linked list==>

Enter no. of nodes==>3

Enter values of nodes==>3 5 1

Created link list==>

                head--->3--->5--->1--->NULL

After sorting linked list==>

                head--->1--->3--->5--->NULL

Create normal linked list==>

Enter no. of nodes==>4

Enter values of node==>2 7 6 3

Created link list==>

                head--->2--->3--->6--->7--->NULL

After merging final list is==>

                head--->1--->2--->3--->3--->5--->6--->7--->NULL