PRG5.合并两个非递减有序链表

设计一个函数 void merge(List La, List Lb) , 其功能是将Lb合并到La中，其中La和Lb的元素均为非递减有序排列，且合并后的La的元素也为非递减有序排列。

//非递减有序排列即关键字递增序排列,但是并非单调递增(因为有重复的关键字)

#include <stdio.h>
#include <stdlib.h>

//其中List是如下结构体：
typedef struct T_Node {
	int d;
	struct T_Node* next;
} Node, * List;

/*设计一个函数
	void merge(List La, List Lb)
其功能是将Lb合并到La中，其中La和Lb的元素均为非递减有序排列，且合并后的La的元素也为非递减有序排列。*/
void merge(List La, List Lb)
{
	Node* pre, * p, * q;//定义指针
	pre = La;//pre指向La头结点
	p = La->next;//p指向La首元结点
	q = Lb->next;//q指向La首元结点
	while (p && q)//当p、q所指均不为空时
	{
		if (p->d < q->d)//如果p所指结点的值小于q所指
		{
			pre->next = p;//将p所指结点链接在pre所指结点后
			pre = p;//pre指向p所指结点
			p = p->next;//p后移一位
		}
		else//否则，即q所指结点的值小于p所指
		{
			pre->next = q;//将q所指结点链接在pre所指结点后
			pre = q;//pre指向q所指结点
			q = q->next;//q后移一位
		}
	}
	if (p)	pre->next = p;//如果p所指不为空，即La尚未遍历完，则全部链接在pre所指结点后
	else	pre->next = q;//同理
	free(Lb);//释放掉Lb链表
}


//当执行如下的main函数后
void main()
{
	List La, Lb;
	Node* p, * q;
	int i;

	La = (List)malloc(sizeof(Node));
	p = La;
	Lb = (List)malloc(sizeof(Node));
	q = Lb;

	for (i = 1; i <= 10; i++)
	{
		p->next = (Node*)malloc(sizeof(Node));
		p->next->d = 2 * i;
		p->next->next = NULL;
		p = p->next;

		q->next = (Node*)malloc(sizeof(Node));
		q->next->d = 3 * i - 2;
		q->next->next = NULL;
		q = q->next;
	}
	merge(La, Lb);
	p = La->next;
	//printf("\n\n\n");
	while (p != NULL)
	{
		printf(" %d   ", p->d);
		p = p->next;
	}
	printf("\n");
}
/*执行的结果为
1    2    4    6    7    8    10    12    13    14    16    18    19    20    22    25    28*/