例2-11 已知两个链表（头指针分别为 La 和 Lb）中的数据元素均自小至大有序，编写算法将这两个链表归并为一个链表。再看一个有序表操作的例子。
解题分析：
通常容易想到的这个题的做法是，将 Lb 表中的各个结点插入到 La 表中的相应位置中去。即按照有序关系首先查找插入位置，然后修改相应指针。另一种做法是，受例2-9中分析的启发，试设想新建一个空的链表，然后将已知两个链表中的结点依从小到大的次序逐个插入到这个新的链表中。
算法2.25void MergeList_L(LinkList &La, LinkList &Lb, LinkList &Lc)
{
// 已知单链线性表 La 和 Lb 的元素按值非递减排列。本算法
// 归并 La 和 Lb 得到新的单链线性表 Lc，Lc 的元素也按
// 值非递减排列。操作之后 La 和 Lb 消失
pa = La->next; pb = Lb->next;
Lc = rc = new LNode; // 建空表，Lc 为头指针
pa 和 pb 分别指向 La 表和 Lb 表中第一个结点，rc 指示 Lc 表当前的表尾结点。
{
if (pa->data <= pb->data)
{ // 将 *pa 插入Lc表，指针 pa 后移
rc->next = pa; rc = pa; pa = pa->next;
} // if
else
{ // 将 *pb 插入Lc表，指针 pb 后移
rc->next = pb; rc = pb; pb = pb->next;
} // else
} // while
比较结点 *pa 和 *pb 中的数据元素，并将其中"小者"链接到 Lc 表的表尾直至其中一个表为空止。
delete(La); delete(Lb); // 释放 La 和 Lb 的头结点
} // MergeList_L
显然，此算法的时间复杂度为O (ListLength(La)+ListLength(Lb))。
|
|||
|
不知你是否注意到，算法中没有设置Lc表表尾的语句，那么，在算法结束之后，Lc的表尾是否"正常"结束了呢？