LeetCode总结 -- 一维数据合并篇

合并是一维数据结构中很常见的操作， 通常是排序， 分布式算法中的子操作。 这篇总结主要介绍LeetCode中关于合并的几个题目：
Merge Two Sorted Lists
Merge Sorted Array
Sort List
Merge k Sorted Lists

我们先来看看两个有序一维数据的合并， 这里主要是要介绍链表的合并操作， 不过因为一维数组的合并也比较简单， 而且与链表有比较性， 就顺便在这里列举一下。 Merge Two Sorted Lists就是要求合并两个有序链表， 一般来说合并的思路就是以一个为主参考， 然后逐项比较， 如果较小元素在参考链表中， 则继续前进， 否则把结点插入参考链表中， 前进另一个链表， 最后如果另一个链表还没到头就直接接过来就可以了， 思路和实现都比较简单， 最好力求一遍过哈。 Merge Sorted Array也是一样的思路， 只是数据结构换成了一维数组， 所以插入操作比链表要麻烦一些， 这里相当于从尾部开始， 然后数字一个个按照位置填入， 插入操作在这里就不明显了。 可以看出虽然思路近似， 但是数据结构不同， 因为操作不同， 实现细节还是比较不一样的， 都得熟练掌握哈。
有了上面合并两个链表（或者数组）我们就可以进行归并排序了， 也就是Sort List这道题目。 对于链表， 用Merge Two Sorted Lists作为合并的子操作， 然后用归并排序的递归进行分割合并就可以了， 这里就不说排序的具体细节了， 会有专门的排序总结篇哈。

最后我们来说说最重要的也是最实用的一个题目Merge k Sorted Lists。 为什么说他实用是因为现在分布式系统很多， 而且也很强调MapReduce或者Hadoop的技术， 这个题目就是分布式计算的一个常见操作。 比如说来自不同client的有序数据要在central server上面进行合并。 这个问题有两种做法：
第一种就是利用上面的Merge Two Sorted Lists对k个链表先进行两两合并， 然后再上一层继续两两合并， 直到合成一个链表。 根据Merge k Sorted Lists中的分析， 时间复杂度是O（nklogk）, 空间复杂度是O（logk）。
上面这种做法是利用分治然后进行合并的方法， 接下来这个方法用到了堆的数据结构。 思路是维护一个大小为k的堆， 每次取堆顶的最小元素放到结果中，然后读取该元素对应的链表的下一个元素放入堆中。 因为每个链表是有序的， 每次又是去当前k个元素中最小的， 所以当所有链表都读完时结束，这个时候所有元素按从小到大放在结果链表中。 这个算法每个元素要读取一次，即k*n次，然后每次读取元素要把新元素插入堆中要O（logk）的复杂度，所以复杂度是O(nklogk)， 跟第一种方法是一样的。
两种方法不同的数据结构和类型， 都非常具有代表性， 个人觉得都很有意思哈。

合并算是链表中比较典型的操作， 也能够连续地问出比较连贯的一些题目， 扩展性非常好， 既可以考察基本数据结构的操作， 又可以看看对于算法和更多数据结构的理解， 是一个不错的面试话题。