【数据结构】有序链表合并（归并）问题的一种解决思路

【背景】

设计一个程序，将两个递增的有序链表合并成一个递减的有序链表，要求结果链表仍使用原来两个链表的存储空间，合并后不允许有重复的数据。

（本题取自广西师范大学2018年硕士研究生招生考试试题编程题部分）。

【源码运行环境】

操作系统：Windows 10

编译环境：Dev C++(基于C99标准)

【思路】

在背景题干中，我们知道，初始化有序的链表是递增的。而在我们学习数据结构中，我们是实现过将两个递增的链表合并成一个递增的链表这样的功能。

奈何，题干中的要求并非递增。

于是我们可以换个想法，是否可以综合我们所学的知识：

1、先合并成递增

2、再转置成递减。

由于时间有限，具体实现不赘述，此处给出递增合并单链表的算法；

链表创建即常用操作定义、链表转置的算法可以参照我之前的文章：

1、【数据结构】线性表的C语言实现

2、【数据结构】单向链表的反转/倒置的一种实现方法

【伪代码】

void MergeList(LinkList &La, LinkList &Lb, LinkLisk &Lc)
{
    pa=La->next;
    pb=Lb->next;
    Lc=pc=La;
    while(pa && pb)
    {
        if(pa->data < pb->data)
        {
            pc->next = data;
            pc = pa;
            pa = pa->next;
        }
        else if(pa->data > pb->data)
        {
            pc->next = pb;
            pc = pb;
            pb = pb->next;
        }
        else
        {
            pc->next = pa;
            pc=pa;
            pa=pa->next;
            q=pb->next;
            delete pb;
            pb=q;
        }
    }
    pc->next = pa?pa:pb;
    delete b;
}

【总结】

由于作者最近刚换平台（从Mac OS X -> Windows），基于链表指针的调试涉及到编译环境的调试。复习时间有限，没能够及时地将代码实现，故给出《数据结构习题解析与实验指导》中关于归并递增链表的算法。其余算法已经证实可以在基于Cmake环境下进行实验。等闲下来再讲此算法进行完善。

本题也透露出一种程序设计思想：我们在有限时间内，要针对某项任务编写程序时，可以将需求进行细分，不一定得死磕需求字眼；这也是一种大化小，小化无。分而治之的程序设计思想。

【参考文献】

• 《大话数据结构》.程杰.清华大学出版社

• 《数据结构习题解析与实验指导》.李冬梅,张琪.人民邮电出版社

• 广西师范大学2018年硕士研究生招生考试《806/826 数据结构》试题