2.6.4　典型例题解析

【例2-3】已知两个单链表A和B，其中的元素都是非递减排列，编写算法将单链表A和B合并得到一个递减有序的单链表C（值相同的元素只保留一个），并要求利用原链表结点空间。

【分析】此题为单链表合并问题。利用头插法建立单链表，使先插入元素值小的结点在链表末尾，后插入元素值大的结点在链表表头。初始时，单链表C为空（插入的是C的第一个结点），将单链表A和B中较小的元素值结点插入C中；单链表C不为空时，比较C和将插入结点的元素值大小，值不同时插入到C中，值相同时，释放该结点。当A和B中有一个链表为空时，将剩下的结点依次插入C中。程序的实现代码如下：

程序的运行结果如图2-30所示。

图2-30　合并单链表的程序运行结果

在将两个单链表A和B的合并算法MergeList中，需要特别注意的是，不要遗漏单链表为空时的处理。当单链表为空时，将结点插入C中，代码如下：

对于初学者而言，写完算法后，一定要上机调试一下算法的正确性。

【例2-4】利用单链表的基本运算，求两个集合的交集。

【分析】假设A和B是两个带头结点的单链表，分别表示两个给定的集合A和B，求C=A带头。先将单链表A和B分别从小到大排序，然后依次比较两个单链表中的元素值大小，pa指向A中当前比较的结点，pb指向B中当前比较的结点，如果pa->data<pb->data，则pa指向A中下一个结点；如果pa->data>pb->data，则pb指向B中下一个结点；如果pa->data==pb->data，则将当前结点插入C中。

程序实现如下：

程序的运行结果如图2-31所示。

图2-31　求A和B交集的程序运行结果