Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
与21. Merge Two Sorted Lists的拓展，这道题要合并k个有序链表。
解法1: 两两合并。1和2合并，结果在和3合并，以此类推，直到结束。时间复杂度为：2n + 3n + ... + kn = [(k+1)*k/2-1]*n = O(nk^2)，空间复杂度为O(1)
解法2: 分治法Divide and Conquer，也就是二分法。每次将所有的list两两之间合并，直到所有list合并成一个。时间复杂度：2n * k/2 + 4n * k/4 + ... + (2^x)n * k/(2^x) = O(nklogk)，如果用迭代空间复杂度为O(1)，用递归则空间复杂度为O(logk)。
解法3: 最小堆MinHeap/priority queue，取每个Linked List的最小节点放入一个heap中，排序成最小堆，取出堆顶最小的元素，放入合并的list中，然后将该节点在其list中的下一个节点插入heap，循环上面步骤，以此类推直到全部节点都经过heap。由于heap的大小为始终为k，而每次插入的复杂度是logk，一共插入了nk个节点。时间复杂度为O(nklogk)，空间复杂度为O(k)。
Python: Merge two by two, Time: O(nk^2), Space: O(1)
class Solution(object):
def mergeKLists(self, lists):
def mergeTwoLists(l1, l2):
curr = dummy = ListNode(0)
while l1 and l2:
if l1.val < l2.val:
curr.next = l1
l1 = l1.next
else:
curr.next = l2
l2 = l2.next
curr = curr.next
curr.next = l1 or l2
return dummy.next
if not lists:
return None
left, right = 0, len(lists) - 1;
while right > 0:
if left >= right:
left = 0
else:
lists[left] = mergeTwoLists(lists[left], lists[right])
left += 1
right -= 1
return lists[0]
Python: Divide and conquer, Time: O(nklogk), Space: O(logk)
class Solution2:
def mergeKLists(self, lists):
def mergeTwoLists(l1, l2):
curr = dummy = ListNode(0)
while l1 and l2:
if l1.val < l2.val:
curr.next = l1
l1 = l1.next
else:
curr.next = l2
l2 = l2.next
curr = curr.next
curr.next = l1 or l2
return dummy.next
def mergeKListsHelper(lists, begin, end):
if begin > end:
return None
if begin == end:
return lists[begin]
return mergeTwoLists(mergeKListsHelper(lists, begin, (begin + end) / 2), \
mergeKListsHelper(lists, (begin + end) / 2 + 1, end))
return mergeKListsHelper(lists, 0, len(lists) - 1)
Python: Heap, Time: O(nklogk), Space: O(k)
mport heapq
class Solution3:
def mergeKLists(self, lists):
dummy = ListNode(0)
current = dummy
heap = []
for sorted_list in lists:
if sorted_list:
heapq.heappush(heap, (sorted_list.val, sorted_list))
while heap:
smallest = heapq.heappop(heap)[1]
current.next = smallest
current = current.next
if smallest.next:
heapq.heappush(heap, (smallest.next.val, smallest.next))
return dummy.next
C++: Merge two by two
class Solution {
public:
ListNode *mergeKLists(vector<ListNode *> &lists) {
ListNode *ret = NULL;
for(int i=0; i<lists.size(); i++)
ret = merge2Lists(ret, lists[i]);
return ret;
}
ListNode* merge2Lists(ListNode *h1, ListNode *h2) {
ListNode *dummy = new ListNode(0), *tail = dummy;
while(h1 && h2) {
if(h1->val<=h2->val) {
tail->next = h1;
h1 = h1->next;
}
else {
tail->next = h2;
h2 = h2->next;
}
tail = tail->next;
}
tail->next = h1 ? h1 : h2;
return dummy->next;
}
};
C++: Divide and Conque
class Solution {
public:
ListNode *mergeKLists(vector<ListNode *> &lists) {
if(lists.empty()) return NULL;
int end = lists.size()-1;
while(end>0) {
int begin = 0;
while(begin<end) {
lists[begin] = merge2Lists(lists[begin], lists[end]);
begin++;
end--;
}
}
return lists[0];
}
ListNode* merge2Lists(ListNode *h1, ListNode *h2) {
ListNode *dummy = new ListNode(0), *tail = dummy;
while(h1 && h2) {
if(h1->val<=h2->val) {
tail->next = h1;
h1 = h1->next;
}
else {
tail->next = h2;
h2 = h2->next;
}
tail = tail->next;
}
tail->next = h1 ? h1 : h2;
return dummy->next;
}
};
C++: priority queque
class Solution {
public:
struct compNode {
bool operator()(ListNode *p, ListNode *q) const {
return p->val>q->val;
}
};
ListNode *mergeKLists(vector<ListNode *> &lists) {
priority_queue<ListNode*, vector<ListNode*>, compNode> pq;
ListNode *dummy = new ListNode(0), *tail = dummy;
for(int i=0; i<lists.size(); i++)
if(lists[i]) pq.push(lists[i]);
while(!pq.empty()) {
tail->next = pq.top();
tail = tail->next;
pq.pop();
if(tail->next) pq.push(tail->next);
}
return dummy->next;
}
};
类似题目：
[LeetCode] 21. Merge Two Sorted Lists 合并有序链表
[LeetCode] 88. Merge Sorted Array 合并有序数组