PAT 2-11 两个有序链表序列的合并（C语言实现）

题目描述：

已知两个非降序链表序列S1与S2，设计函数构造出S1与S2的并集新非降序链表S3。

输入格式说明：

输入分2行，分别在每行给出由若干个正整数构成的非降序序列，用-1表示序列的结尾（-1不属于这个序列）。数字用空格间隔。

输出格式说明：

在一行中输出合并后新的非降序链表，数字间用空格分开，结尾不能有多余空格；若新链表为空，输出“NULL”。

样例输入与输出：

1 3 5 -1
2 4 6 8 10 -1

1 2 3 4 5 6 8 10

1 2 3 4 5 -1
1 2 3 4 5 -1

1 1 2 2 3 3 4 4 5 5

-1
-1

NULL

#include<stdio.h>

typedef struct node *ptrNode;
typedef ptrNode LinkList;  //头结点
typedef ptrNode Position;//中间节点
typedef int ElementType;
struct node{
	ElementType Element;
	Position next;
};

int IsEmpty(LinkList L)
{
	return L->next == NULL;
}

LinkList creatList(void)              
{
	LinkList head,r,p;
	int x;
	head = (struct node*)malloc(sizeof(struct node));    //生成新结点
	r = head;
	scanf("%d",&x);

	while(x != -1){
		p = (struct node*)malloc(sizeof(struct node));
		p->Element = x;
		r->next = p;
		r = p;
		scanf("%d",&x);
	}
	r->next = NULL;
	return head;
}

LinkList mergeList(LinkList a, LinkList b)
{
	Position ha, hb,hc;
	LinkList c,r,p;

	ha = a->next;
	hb = b->next;
	
	c = (struct node*)malloc(sizeof(struct node));
	r = c;
	while((ha != NULL)&&(hb != NULL)){
		p = (struct node*)malloc(sizeof(struct node));
		if(ha->Element <= hb->Element){
			p->Element = ha->Element;
			ha = ha->next;
		}
		else{
			p->Element = hb->Element;
			hb = hb->next;
		}

		r->next = p;
		r = p;
	}
	if(ha == NULL){
		while(hb != NULL){
			p = (struct node*)malloc(sizeof(struct node));
			p->Element = hb->Element;
			hb = hb->next;
			r->next = p;
		    r = p;
		}
	}
	if(hb == NULL){
		while(ha != NULL){
			p = (struct node*)malloc(sizeof(struct node));
			p->Element = ha->Element;
			ha = ha->next;
			r->next = p;
		    r = p;
		}
	}

	r->next = NULL;

	return c;
}

void printList(LinkList L)
{
	LinkList hc;
	int flag = 0;

	hc = L->next;
	if(hc == NULL)
		printf("NULL");
	while(hc != NULL){
		if(flag)
			printf(" ");
		else
			flag = 1;
		printf("%d",hc->Element);
		hc = hc->next;
	}
}

int main(void)
{
	LinkList L1,L2,L3;

	L1 = creatList();
	L2 = creatList();

	L3 = mergeList(L1,L2);
	
	printList(L3);

	return 0;
}