学步园

1、假设有两个按元素值递增次序排列的线性表，均以单链表形式存储。请编写算法将这两个单链表归并为一个按元素值递减次序排列的单链表，并要求利用原来两个单链表的结点存放归并后的单链表

分析：此题主要考察的是在链表头部增加结点与链表尾部增加结点的两种区别

List Union( List La, List Lb )
//La,Lb分别是带头结点的两个单链表的头指针，链表中的元素值按递增排列
//本算法实现将La,Lb合并成一个按元素之递减排列的单链表
{
	Lnode pa,pb,pTmp;
	pa = La->next;
	pb = Lb->next;
	La->next = NULL;//La作为结果链表的头指针，初始化结果链表为空
	
	while ( pa&&pb ) {
		if ( pa->data <= pb->data ) {
			pTmp = pa->next;
			pa->next = La->next;
			La->next = pa;
			pa = pTmp;
		}
		else {
			pTmp = pb->next;
			pb->next = La->next;
			La->next = pb;
			pb = pTmp;
		}
	}
	
	if ( pa ) {
		pb = pa;//不论pa或pb不为空，只最后处理pb
	}
	while ( pb ) {
		pTmp = pb->next;
		pb->next = La->next;
		La->next = pb;
		pb = pTmp;
	}
	return La;
}

//算法时间复杂度讨论：6-10L为初始化，花费时间为常数C；12-25L为算法的主体部分，每次把当前pa，pb所指结点中值较小的加入到结果链表，运行时间为La,Lb中长度较小的；29-34L把La,Lb中剩余未操作的结点加入到结果链表。总的运行时间为O(max(n1,n2))

2、设有两个无头结点的单链表，头指针分别为ha,hb,链中有数据域data，链域next，两链表的数据都按递增存放，现要求将hb表归到ha表中，且归并后ha仍递增有序，归并中ha表中已有的数据若hb中也有，则hb中的数据不归并到ha中，hb的链表在算法中不允许破坏。

分析：与1类似。为处理方便，先加上表头结点，最后再删除之，隐含ha为结果链表。

List Union( List ha, List hb )
//ha,hb是两个无头结点的数据域值递增有序的单链表
//本算法实现将hb中不出现在ha中的数据合并到ha中，同时合并中不破坏hb链表
{
	List head = (List)malloc(sizeof(LNode));
	head->next = ha;
	Lnode pa,pb,pTmp;
	pa = ha;
	pb = hb;
	pTmp = head;//pTmp指向当前待合并结点的前驱
	
	while ( pa&&pb ) {
		if ( pa->data < pb->data ) {
			pTmp->next = pa;
			pTmp = pa;
			pa = pa->next;			
		}
		else if ( pa->data > pb->data ) {
			Lnode Lr = (Lnode)malloc(sizeof(Lnode));
			Lr->data = pb->data;
			pTmp->next = Lr;
			pb = pb->next;
		}
		else {//pa->data == pb->data
			pTmp->next = pa;
			pTmp = pa;
			pa = pa->next;
			pb = pb->next;
		}
	}
	
	if ( pa ) {
		pTmp->next = pa;
	}
	else {
		while ( pb ) {
			Lnode  Lr = (Lnode)malloc(sizeof(Lnode));
			Lr->data = pb->data;
			pTmp->next = Lr;
			pTmp = Lr;
			pb = pb->next;
		}
		pTmp->next = NULL;
	}
	
	free(head);
	return ha;
}

此解法相当于把ha与hb合并到Head链表，而不是每次判断ha链表中当前指针所指元素与hb中当前指针元素之间的关系。

第2题解法2：相当于把hb中元素插入ha

List Union( List ha, List hb )
{
	List head = (Lnode)malloc(sizeof(Lnode));
	head->next = ha;
	
	Lnode pa,pa,pTmp;
	pa = ha;
	pb = hb;
	pTmp = ha;
	
	while ( pa&&pb ) {
		if ( pa->data < pb->data ) {
			pTmp = pa;
			pa = pa->next;
		}
		else if ( pa->data > pb->data ) {
			Lnode Lr = (Lnode)malloc(sizeof(Lnode));
			Lr->data = pb->data;
			Lr->next = ha;
			pTmp->next = Lr;
			pTmp = Lr;
			pb = pb->next;
		}
		else {
			pTmp = pa;
			pa = pa->next;
			pb = pb->next;
		}
	}
	
	if ( pa ) {
		pTmp->next = pa;
	}
	else {
		while ( pb ) {
			Lnode Lr = (Lnode)malloc(sizeof(Lnode));
			Lr->data = pb->data;
			pTmp->next = Lr;
			pTmp = Lr;
			pb = pb->next;
		}
		pTmp->next = NULL;
	}
	
	free(head);
	return ha;
}

3、指针为ha和hb的两线性表A和B分别表示两个集合。两表中的元素皆为递增有序。请写一算法求A和B的并集A∪B。要求该并集中的元素仍保持递增有序。且要利用A和B的原有结点空间。

List Union( List ha, List hb )
{
	LNode pa = ha->next;
	LNode pb = hb->next;
	LNode pre = ha;//pre表示结果链表当前结点的前驱指针
	
	while ( pa && pb ) {
		if ( pa->data < pb->data ) {
			pre->next = pa;
			pre = pa;
			pa = pa->next;
		}
		else if ( pa->data > pb->data ) {
			pre->next = pb;
			pre = pb;
			pb = pb->next;
		}
		else { //pa->data == pb->data
			LNode pTmp = pb;
			pre->next = pa;
			pre = pa;
			pa = pa->next;
			pb = pb->next;
			free( pTmp );
		}
	}
	if ( pa ) {
		pre->next = pa;
	}
	else {
		pre->next = pb;
	}
	
	return ha;
}

应该是3个题里面最简单的。