如果你能解出这道算法题就去面BAT吧

这是LeetCode上个人比较喜欢的一个题目，Merge k Sorted Lists，也就是合并k个有序链表，比如给定链表：

[  1->4->5,  1->3->4,  2->6]

将其合并后的有序链表是：1->1->2->3->4->4->5->6。

这个题目有一定的难度，如果你能无bug的写出代码就去面一下BAT吧。

那么该怎么解决这个问题？

比较容易想到的思路

一般像这类算法问题都有一个最最简单最最直观的解法，大不了我们遍历一边所有链表，把数字装入数组中，然后对数据进行排序，将排好序的数组再放到链表中，这已经是最简单的解法了，该过程如图所示：

对数组[1,4,5,1,3,4,2,6]进行排序得到[1,1,2,3,4,4,5,6]，再将该数组转为链表：

显然这个解法的时间复杂度为O(NlogN)，空间复杂度为O(N)，其中N为链表所有节点的个数。

有的同学可能会说这种解法没有利用到给定链表是有序的特点，我们可以利用这个特定设置k个指针，开始时k个指针指向各个链表的起始节点，那么这k个节点中最小的那个一定就是最后有序链表的第一个节点，这是显而易见的，找到k个节点中最小的那个后将对应的指针前进一步，我们不断重复这个过程最终就能得到有序链表了，这个过程如图所示，我们只取前三步：

那么这种解法的时间复杂度是多少呢？

每次比较k个数才能获取一个最终节点，整个链表有N个节点，因此时间复杂度为O(kN)，由于不需要借助额外空间因此时间复杂度为O(1)，这已经优于第一种解法了，如果k比LogN小的话。

有的同学可能会说，那如果将这k个链表一个挨一个的合并呢？可以证明这种解法的时间复杂度同样也是O(kN)，空间复杂度O(1)，并不优于第二种解法。

那么有没有更优解吗，答案是肯定的。

算法优化

对于归并排序想必大家都比较熟悉，归并排序的思想是我们先对数组中的数两两合并，对得到的有序片段再次两两合并直到形成一个有序片段，这个有序片段就是最后的解了。

归并排序的思想在计算机科学中有着极为重要的地位，因为归并算法首次向人们展示了“分而治之”这种思想的威力，对其后的算法设计产生了深远的影响。

那么回到这里该怎么将归并思想应用到这个题目呢？

实际上也很简单，那就是我们先把给定的链表序列两两合并，这样我们就得到了一个新的有序链表序列，然后再次两两合并直到生成一个有序链表为止，该过程如图所示：

我们可以简单计算一下，由于链表总数为N个，在每一层的合并中算法复杂度为O(N)，那么需要多少层呢，显然是Logk层，因此该算法的时间复杂度为O(Nlogk)，空间复杂度为O(1)，毫无疑问该算法相对于前几个都有了很大的优化。

代码实现

ListNode* merge_1(ListNode* l1,ListNode*l2){    ListNode n(0);    ListNode* p = &n;    while(l1&&l2){        if (l1->valval){            p->next = l1;            l1=l1->next;        } else {            p->next = l2;            l2=l2->next;        }        p = p->next;    }    p->next=l1?l1:l2;    return n.next;}ListNode* mergeklist(vector& lists,int b,int e){    if (b>e)        return NULL;    if (b==e)        return lists[b];    int m = (b+e)/2;    return merge_1(mergeklist(lists, b, m),                   mergeklist(lists,m+1,e));}ListNode* mergeKLists(vector& lists) {    return mergeklist(lists, 0, lists.size()-1);}

总结

在这个题目中我们首次介绍了分而治之这种思想，这实际上是一种很朴素的解决问题的方法，当然不仅限于计算机领域，生活当中如果你留心的话也会发现这种思想的应用，在后续题目中我们还会多次见到这种思想的使用，之后我们会针对各种算法思想进行详细讲解，敬请期待。