问题

Merge k Sorted Lists ： https://leetcode.com/problems/merge-k-sorted-lists/

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

解析

本题难点在于：如何在k个链表结点中，选择最小的一个；如何剔除已经为空的链表

1 逐个合并2个链表

由merge两个有序链表可联想到，我们可以逐个合并2个链表，直到所有合并完成
假设每个链表长度为n，有k个链表
时间复杂度：$O(k^2n)$ ,空间$O(1)$
如上所示，等价问题是对于k个数进行排序，时间复杂度是$O(k^2)$, 需要排列n次

struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2); struct ListNode* mergeKLists(struct ListNode** lists, int listsSize) {//k个数选最小，剔除为空的链表if (listsSize == 0)return NULL;struct ListNode* l = lists[0];int i = 1;while (i < listsSize) {l = mergeTwoLists(l, lists[i]);i++;}return l;
}

上述程序运行超时，说明算法的时间的复杂度不满足要求。

2 merge-sort

此时，我们考虑如何降低运行时间，能否实现对k个数排序，得到$O(k\ lgk)$, 采用merge-sort的方法，先把k个list分成两半，然后继续划分，知道剩下两个list就合并起来，合并时会用到Merge Two Sorted Lists中的算法实现。
C++语言实现 ：时间复杂度 $O(nklgk)$ 空间复杂度 O(1)

/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode(int x) : val(x), next(NULL) {}* };*/
//时间复杂度 O(nklgk), 空间复杂度 O(1)
class Solution {
public:ListNode* mergeKLists(vector<ListNode*>& lists) {if (lists.size() == 0)return NULL;return mergeR(lists, 0, lists.size()-1);}
private:ListNode* mergeR(vector<ListNode*> &lists, int l, int r) {if (l < r) {int m = (l+r) / 2;return mergeTwoLists(mergeR(lists, l, m), mergeR(lists, m+1, r));}return lists[l];}
private:ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {if (l1 == NULL)return l2;if (l2 == NULL)return l1;ListNode dummy(-1);ListNode* prev = &dummy;while (l1 && l2) {if (l1->val < l2->val) {prev->next = l1;l1 = l1->next;} else {prev->next = l2;l2 = l2->next;}prev = prev->next;}if (l1 == NULL)prev->next = l2;elseprev->next = l1;return dummy.next; }
};

3 堆实现

既然merge-sort是为了加快找到最小结点的速度，可以利用堆的性质。
维护一个大小为k的堆，每次将堆顶的元素（最小）返回到结果中，然后将堆顶的下一个元素压入堆中，然后维护堆的性质（$O(lgk)$）。因为链表是有序的，每次又是去k个元素中最小的，当所有链表都读取结束时，所有元素都按照从小到大排列到结果链表中。此算法需要读取每个元素1次，即n*k次，每次将新元素插入到堆中，需要O(lg k)，所以总的时间复杂度为$O(nklg\ k)$， 空间复杂度即堆的大小$O(k)$

以下代码中使用了STL优先队列#include <queue>，使用方法可参考
STL 栈，队列，优先队列用法 http://blog.csdn.net/crayondeng/article/details/16332169

C++实现：

class Solution {
public:ListNode* mergeKLists(vector<ListNode*>& lists) {if (lists.size() == 0)return NULL;ListNode dummy(-1);ListNode* prev = &dummy;priority_queue<ListNode*, vector<ListNode*>, cmp2 > heap;for (int i = 0; i < lists.size(); i++) {if (lists[i]) {heap.push(lists[i]);}}while (heap.size() > 0) {ListNode* cur = heap.top();heap.pop();prev->next = cur;prev = prev->next;if (cur->next != NULL)heap.push(cur->next);}return dummy.next;}
private:struct cmp2 //操作符重载,实现小元素优先{bool operator ()(ListNode* x, ListNode* y) {return x->val > y->val;}};
};

总结

上述3中方法的时间复杂度，可以对应于对于k个元素冒泡排序、归并排序、堆排序

参考资料

http://blog.csdn.net/linhuanmars/article/details/19899259