整理严蔚敏版数据结构课后习题重点算法：合并递增有序链表

本算法的题目是将两个递增的有序链表合并为一个递增的有序链表，要求结果链表仍然使用原来两个链表的存储空间，不另外占用其他的存储空间，并且表中不允许有重复的数据。 算法的关键点在于如何在合并过程中删除重复的数据，并且仍然保持链表的有序性。 首先，我们可以定义三个工作指针，分别是头指针Lc、链表La的工作指针pa，和链表Lb的工作指针pb。其中，头指针Lc指向合并结果链表的第一个节点，pa指向链表La的第一个节点，pb指向链表Lb的第一个节点。 接下来，我们从链表的第一个节点开始进行比较。如果pa和pb都没有到达各自链表的表尾节点，我们将pa和pb所指向的节点中的较小值摘取下来，然后链接在Lc链表的最后。如果两个节点的值相等，则只摘取La链表中的节点，删除Lb链表中的节点，这样可以确保合并后的链表中不会出现重复的值。 当某个链表到达了表尾节点为空时，我们将另一个非空链表中剩余的节点直接链接在Lc链表的最后。 最后，返回头指针Lc，即为合并结果链表。 具体算法描述如下： void MergeList(LinkList La, LinkList Lb, LinkList &Lc) { // 初始化工作指针 Lc = pa = La->next; pb = Lb->next; // 用于记录上次插入的节点 LinkList last = Lc; while (pa && pb) { // 比较节点的值 if (pa->data < pb->data) { last->next = pa; last = pa; pa = pa->next; } else if (pa->data > pb->data) { last->next = pb; last = pb; pb = pb->next; } else { // 相等时只摘取La链表中的节点，删除Lb链表中的节点 pa = pa->next; pb = pb->next; } } // 链接剩余的节点 last->next = pa ? pa : pb; // 将多余的节点置为空，以防止出现意外的错误 La->next = NULL; Lb->next = NULL; } 这个算法在合并过程中遍历了两个链表，每次比较和摘取操作都只需要常数时间，所以整个算法的时间复杂度为O(n)，其中n为两个链表中节点的总数。 这个算法不需要使用额外的存储空间，只需要用到了几个工作指针和常数个辅助变量，所以空间复杂度为O(1)。 总结来说，这个算法通过比较节点的值，将较小的节点摘取下来，并链接在合并结果链表的最后。在比较过程中，还会删除重复的节点，以确保合并后的链表中不会出现重复的值。这个算法具有时间和空间效率较高的特点，适用于合并有序链表并删除重复元素的场景。