【问题描述】

将两个非递减的有序链表合并为一个非递增的有序链表。要求结果链表仍使用原来两个链表的存储空间，不另外占用其他的存储空间。表中允许有重复的数据。

【参考代码】

typedef struct LNode
{
	int data;
	struct LNode* next;
}LNode, *LinkList;
void MergeList(LinkList &La, LinkList &Lb, LinkList &Lc)
{
	LinkList pa, pb, q;
	pa = La->next;
	pb = Lb->next;
	Lc = La;
	Lc->next = NULL; //采用头插法
	while (pa && pb)
	{
		if (!pa)
		{
			q = pb;
			pb = pb->next;
		}
		if (!pb)
		{
			q = pa;
			pa = pa->next;
		}
		if (pa->data > pb->data)
		{
			q = pa;
			pa = pa->next;
		}
		else
		{
			q = pb;
			pb = pb->next;
		}
		q->next = Lc->next;
		Lc->next = q;
	}
	delete Lb;
}

【代码讲解】

本代码针对考研数据结构，采用伪代码，主要理解代码思路，由于原链表是有重复数的升序序列，要求改降序，且不能占用其他存储空间，所以只能采用头插法进行。