007　合并两个单链表

已知两个单链表A和B，其中的元素都是非递减排列，编写算法将单链表A和B合并得到一个递减有序的单链表C（值相同的元素只保留一个），并要求利用原链表结点空间。例如A={12，16，21，33，35，87，102}，B={3，5，21，23，35，99，123}，则合并后C为{123，102，99，87，35，33，23，21，16，12，5，3}。

【分析】

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

第1章\范例01-08.c

运行结果（见图1.21）

图1.21　算法运行效果