#include<stdio.h>
#include<stdlib.h>
//node结点
typedef struct node{
	int data;
	struct node *next;
}*LinerList;
//排序法
void paixu(LinerList head,int n)
{
	int i=0,j=0,temp;
	LinerList p2;
	LinerList p1;

	for(p1=head;i<n-1;i++,p1=p1->next)
		for(p2=p1->next;j<n-i-1;j++,p2=p2->next)
		{
			if(p1->data>p2->data)
			{
				temp=p2->data;
				p2->data=p1->data;
				p1->data=temp;
			}
		}

}
//新建一个链表
void CreateLinerList(LinerList *head,int n)
{
	int data;
	LinerList p,tail;
	printf("请输入链表对应的数据元素:\n");
	scanf("%d",&data);
	p=(LinerList)malloc(sizeof(struct node));
	p->data=data;
	p->next=*head;
	*head=p;
	tail=p;
	while(n>1)
	{
		scanf("%d",&data);
		p=(LinerList)malloc(sizeof(struct node));
	    p->data=data;
	    p->next=NULL;
	    tail->next=p;
		tail=p;
		n--;
}
}
//显示一个链表
void Show(LinerList p)
{
	while(p!=NULL)
	{
		printf("%-6d",p->data);
		p=p->next;
	}
	printf("\n");
}
//归并两个链表
void Combine(LinerList* ha,LinerList hb)
{
	LinerList current,last,other;
    while(hb!=NULL)
	{
		other=(LinerList)malloc(sizeof(struct node));
		other->data=hb->data;
		current=*ha;
		while(other->data>current->data&&current->next!=NULL)
		{
			last=current;
			current=current->next;
		}
		if(other->data<=current->data)
			if(current==*ha)
			{
				other->next=*ha;
				*ha=other;
				hb=hb->next;
			}
			else
				if(other->data==current->data)
			{
				hb=hb->next;
			}
			 else{
				other->next=current;
				last->next=other;
				hb=hb->next;}
			 else{
				 other=hb;
				 current->next=other;
			 }
			 }
}
int main()
{
	LinerList ha=NULL,hb=NULL;

	int a,b;
	printf("请输入ha的数据个数a:\n");
	scanf("%d",&a);
	CreateLinerList(&ha,a);
	paixu(ha,a);

	printf("请输入hb的数据个数b:\n");
	scanf("%d",&b);
	CreateLinerList(&hb,b);
	paixu(hb,b);

	printf("链表ha:");
	Show(ha);
    printf("链表hb:");
	Show(hb);
	printf("\n");
	printf("---------------------------------------------------\n");
	Combine(&ha,hb);
	printf("合并后的链表ha为:");
	Show(ha);
	printf("合并后的链表hb为:");
	Show(hb);
}