合并2个排序列表

合并两个排序的列表在算法上是微不足道的。

从每个列表的第一个元素开始,比较,写下下要输出的较低的元素,并将找到较低的元素的列表向前推进。一直往前走,直到你到达一个列表的末尾,然后把另一个列表的其余部分放出来。

这只需要在每个列表上循环一次,并且每个输出元素最多需要一个比较。

编辑:这和两个列表一样有效。当你有大量的列表要合并时,它会变得(有点)更加棘手。

你可以写一个函数 is-sorted-p 它确定列表是否仍按升序排列。然后连接这两个列表,并随机地无序移动结果,直到它通过谓词。

…你什么都没说。

如果你只有两个,那就相对容易了。

1. 两个列表都是空的吗?如果是这样,结果是一个空列表
2. 一个列表是空的,另一个不是吗?结果是非空列表。
3. 找到最小的列表头(“car”),结果就是该列表头,结果是一个带有该列表尾和另一个列表的自调用的结果。

可以使用一些助手参数(可能还有自定义的“reverse and cons to”助手函数)将其转换为尾部递归过程。

有两种方法可以解决这个问题。

因为有两个链表,而且两个链表都是以最简单的方式在高级别排序的 忽略基本情况。

list_t*
merge(list_t *head_1P, list_t *head_2P) {

      if (head_1P == NULL) {
             return head_2P;
      } else if (head_2P == NULL) {
             return head_1P;
      }

      list_t *temp = NULL;
      list_t *new_headP = NULL;

      while(head_2P != NULL) {
            // Remove one element from
            // the second list.
            temp = head_2P;
            head_2P = head_2P->next;
            temp->next = NULL;

            insert_sort(&head_1P, temp);
      }
}

void
insert_sort(list_t **headP, list_t *temp) {

      if (*headP == NULL || (*headP)->data > temp->data) {

             temp->next = *headP;
             *headP = temp;
             return;
      }

      list_t *currentP = *headP;

      while(currentP->next != NULL) {

            if (currentP->next->data > temp->data) {

                    temp->next = currentP->next;
                    currentP->next = temp;
                    return;
            }

            currentP = currentP->next;
      }

      temp->next = currentP->next; // Assigning NULL.
      currentP->next = temp;
}

为了进一步优化这一点,我们可以对插入进行排序,以重新运行插入的位置。 每次都避免插入。因为在最坏的情况下,如果第二个链表元素都被插入到第一个链表的末尾,这可能需要O(m*n)的时间复杂性。

您要查找的是创建列表的函数的递归定义(通过合并两个列表)。

可以预料,函数将根据某种原理提取head元素,然后从其余元素递归构造list tail,从而创建一个列表。

由于需要返回已排序的列表,因此列表头始终是列表中最小的元素。所以,您需要做的就是找到一个算法,从两个排序的列表中提取最小的元素(这应该很容易,因为它们是排序的)。

如果你的列表可以加倍 balanced binary trees ,可以插入 list2 到 b-tree(list1) 然后再转换成一个列表。