#include<stdio.h>

#include<malloc.h>

typedef int elemtype;

typedef struct node

   { elemtype data;   

    struct node *next; 

    }linklist;

linklist  *creatlist(int n)

 {  

   int x,k;

  linklist *head, *r, *p;

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

  head=p;

  p->next=NULL;

  r=p;

  for(k=1;k<=n;k++)

  { printf("input value:\n");

    scanf("%d",&x);

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

    p->data=x;

    p->next=NULL;

    r->next=p;

    r=r->next;

  }

return(head);

}

linklist  *uni(linklist *heada, linklist *headb)

{ linklist *p, *q,*r;

  p=heada->next;

  q=headb->next;

  r=heada;   

while((p!=NULL)&& (q!=NULL))

{ if(p->data>q->data)

    {r->next=q;

     r=q;

     q=q->next;

    }

else

  if(p->data<=q->data)

   { r->next=p;

     r=p;

    p=p->next;

  }

}

if(q!=NULL)

  r->next=q;

else

  r->next=p;

return(heada);

}

// 以下是主程序

void main()

{ linklist *heada,*headb,*p,a; 

  int n1,n2;

  p=&a;

  printf("input the length of the lista:\n");  

    scanf("%d",&n1);   

  heada=&a;  

  heada=creatlist(n1);

  printf("input the length of the listb:\n");  

    scanf("%d",&n2);   

  headb=&a;  

  headb=creatlist(n2);

  p=uni(heada,headb);

  p=p->next;

  printf("Now output the union list Lc's data:\n");

  while(p!=NULL)

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

   p=p->next;

  }

}