将两个递增的单链表合并为一个递减的单链表

问题描述：

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

问题解答：

算法思想：两个链表已经按元素值递增次序排序，将其合并时，均从第一个结点起进行比较，将小的结点链入链表中，同时后移工作指针。该问题要求结果链表按元素值递减次序排列，故新链表的建立应该釆用头插法。比较结束后，可能会有一个链表非空，此时用头插法将剩下的结点依次插入新链表中即可。

void MergeList(LinkList &La,LinkList &Lb) {
    //合并两个递增有序链表（带头结点)，并使合并后的链表递减排列
    LNode *r, *pa=La->next, *pb=Lb->next;  //分别是表 La 和 Lb 的工作指针
    La->next = NULL;  //La作为结果链表的头指针，先将结果链表初始化为空
    while(pa&&pb)  //当两链表均不为空时，循环
        if(pa->data<=pb->data){
            r=pa->next;  //r暂存pa的后继结点指针
            pa->next=La->next;
            La->next=pa;  //将pa结点链于结果表中，同时逆置(头插法）
            pa=r;  //恢复pa为当前待比较结点
        }else{
            r=pb->next;  //r暂存pb的后继结点指针
            pb->next=La—>next;
            La->next=pb;  //将pb结点链于结果表中，同时逆置(头插法）
            pb=r;  //恢复pb为当前待比较结点
        }
        if(pa)
            pb=pa;  //通常情况下会剩一个链表非空，处理剩下的部分
        while(pb){  //处理剩下的一个非空链表
            r=pb->next;  //依次插入到La中（头插法）
            pb->next = La->next;
            La->next = pb;
            pb=r;
        }
    free(Lb);
}