#include<stdio.h>

#include<stdlib.h>

typedef struct list

{

 int data;

 struct list*next;

}List;

List*hebin(List*head1,List*head2)

{ List*head,*rear;

 if(head1==NULL) return head2;

 if(head2==NULL) return head1;

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

 {

  rear=head=head1;

  head1=head1->next;

  } 

  else

  {

   rear=head=head2;

   head2=head2->next;

  }

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

  {

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

   {

    rear->next=head1;

   rear=head1;

   head1=head1->next; 

   } 

   else

   {

   rear->next=head2;

   rear=head2;

   head2=head2->next;  

   }

  }

  if(head1!=NULL)

   rear->next=head1;

 else

  rear->next=head2;

  return head;

}

List*insert_list_order(List*head,int data)

{ List*newnode=(List*)malloc(sizeof(List));

 List*p=head;

 newnode->data=data;

 newnode->next=NULL;

 if(head==NULL) return newnode;

 if(head->data>data)

 {

  newnode->next=head;

  head=newnode;

  return head;

 }

 while(head->next && head->next->data<data)

 {

  head=head->next;

 }

 if(!head->next) head->next=newnode;

 else

 {

  newnode->next=head->next;

  head->next=newnode; 

 }

 return p;

}

void print_list(List*head)

{

 while(head)

 {

  printf("%d\n",head->data);

  head=head->next;

 }

}

int main()

{

 int i,j;

 List*head1=NULL;

 List*head2=NULL;

 List*head;

 for(i=0;i<10;i+=2)

 {

  head1=insert_list_order(head1,i); 

 }

 printf("head1:\n");

 print_list(head1); 

 for(j=1;j<20;j+=3)

 {

  head2=insert_list_order(head2,j); 

 }

 printf("head2:\n");

 print_list(head2);

 head=hebin(head1,head2);

 printf("head:\n");

 print_list(head); 

}