1

我有一个整数链表，它的前半部分和后半部分都是独立排序的。现在我需要合并两个部分来创建一个单一的排序链表。

样本输入：

输入列表 1：1->2->3->4->5->1->2
输出： 1->1->2->2->3->4->5

输入列表 2：1->5->7->9->11->2->4->6
输出 2：1->2->4->5->6->7->9->11

预期输出：

1,2,3……

4

5 回答 5

2

这是归并排序。

我将保持两个指针：

ptr1指向前半部分的第一个元素

并ptr2指向后半部分的第一个元素。

您将需要一个额外的数组来存储最终列表，当然您可以选择不使用这个额外的数组，但是这个讨论离主题很远。

1，比较*ptr1和*ptr2，如果*ptr1的值小于*ptr2，则将该值（即*ptr1）复制到最终数组中，然后ptr1继续前进。

如果ptr2的值是较小的，只需复制*ptr2并ptr2继续前进

2、指针指向最后一个元素后停止，假设前半部分有5个元素a[0] a[1] a[2] a[3] a[4]，则指针指向时停止 a[5]

3、如果前半部分为空，则复制后半部分的其余部分，反之亦然。

于 2012-11-07T07:55:30.877 回答
0

这称为归并排序。

在这里和这里查看实现细节。

于 2012-11-07T07:47:39.527 回答
0

寻找自然合并排序以获得最佳解决方案：http ://en.wikipedia.org/wiki/Merge_sort#Natural_merge_sort

于 2012-11-07T07:48:30.187 回答
0

我在使用函数式语言时已经做过无数次了，所以我想我可以给你一个简短的解释。

如果您将其视为递归过程，则更容易掌握这个想法，但我会给您一个命令式的。你从你的部分列表和一个空的排序列表开始。

然后你开始你的循环，你的部分列表可以看作：

  • 都是空的，在这种情况下你的处理就完成了，
  • 其中一个为空，您将另一个附加到排序列表中，
  • 几个头部元素和列表的尾部，您将在其中比较两个头部，将最小的添加到排序列表中，将另一个留在原来的位置，然后循环使用剩余的列表。

一旦退出循环，您只需返回排序列表。

但是有一个警告：如果您使用的是简单的链表，则可以通过在排序列表前面添加元素并在最后返回之前将其反转来获得更好的运行时间。

于 2012-11-07T08:06:25.130 回答
0 
int[] merge(int[] left, int[] right) {
        int[] ret = new int[left.length + right.length];

        int i = 0;
        int j = 0;
        for (; i < left.length & j < right.length;) {
            if (left[i] < right[j]) {
                ret[i + j] = left[i++];
            } else if (left[i] > right[j]) {
                ret[i + j] = right[j++];
            } else {
                ret[i + j] = left[i];
                ret[i + j + 1] = left[i];
                i++;
                j++;
            }
        }

        if (i < left.length) {

            copyIntArray(left, i, left.length, ret, ret.length - i);
        } else if (j < right.length) {

            copyIntArray(right, j, right.length, ret, ret.length - j);
        }

        return ret;
    }

    void copyIntArray(int[] src, int startIndex, int endIndex, int[] des, int desStartIndex) {
        for (int i = startIndex; i < endIndex; i++) {
            des[desStartIndex++] = src[i];
        }
    }
于 2019-03-08T13:38:53.477 回答