Leetcode 23. Merge k Sorted Lists (python+cpp)

题目：

解法1：heap

利用heap，保持heap size在k，这边在python里可以用priorityqueue也可以直接用heap。用priorityqueue的话python3不行，因为python3里面定义不太一样：
python3 use from queue import PriorityQueue, instead of from Queue. (the case of ‘Q’)
TypeError ‘<’ not supported between instances of ‘ListNode’ and ‘ListNode’:

python版本的priorityqueue写法：

from Queue import PriorityQueue
class Solution(object):def mergeKLists(self, lists):""":type lists: List[ListNode]:rtype: ListNode"""head = point = ListNode(0)q = PriorityQueue()for l in lists:if l:q.put((l.val, l))while not q.empty():val, node = q.get()point.next = ListNode(val)point = point.nextnode = node.nextif node:q.put((node.val, node))return head.next

python3版本heapq写法：
这边heap的每个元素都是一个tuple，tuple包含两个元素，在heapq进行construct的时候，会调用这个operator ”<“,而比较两个tuple，python默认会从第一个元素开始比较起，这才是这么写正确的原因

class Solution:def mergeKLists(self, lists: List[ListNode]) -> ListNode:h = [(l.val, idx) for idx, l in enumerate(lists) if l]heapq.heapify(h)head = cur = ListNode(None)while h:val, idx = heapq.heappop(h)cur.next = ListNode(val)cur = cur.nextnode = lists[idx].nextlists[idx] = lists[idx].nextif node:heapq.heappush(h, (node.val, idx))return head.next

如果想在python3里面也用priorityqueue的话，你需要重新定义一个类来指导tuple的比较
参加：https://stackoverflow.com/questions/40205223/priority-queue-with-tuples-and-dicts

C++版本heap：
这边需要注意几个点：

• C++里面heap是调用的priorityqueue的接口
• 默认是大根堆，所以需要额外参数定义小根堆
• 利用了pair这个数据结构，两个pair的比较过程是和python里的tuple类似的，默认先比较第一个

typedef pair<int, int> p;class Solution {
    
public:ListNode* mergeKLists(vector<ListNode*>& lists) {
    if (lists.size()==0) return nullptr;ListNode* prehead = new ListNode(0);ListNode* point = prehead;priority_queue<p, vector<p>, greater<p>> pq;for (int i=0;i<lists.size();i++){
    if (lists[i]) pq.push(make_pair(lists[i]->val,i));}while (!pq.empty()){
    auto top = pq.top();pq.pop();point->next = new ListNode(top.first);point = point->next;auto node = lists[top.second]->next;lists[top.second] = lists[top.second]->next;if (node) pq.push(make_pair(node->val,top.second));}return prehead->next;}
};

C++里面如果想要直接传listnode到heap里面去也是可以的，需要重写相应operator的定义，比较复杂，性价比不高

解法2：divide and conquer

两两merge，直到merge成一个链表。这里这个divide and conquer还不是用recursion来实现，而是通过index的变化，比较巧妙

class Solution(object):def mergeKLists(self, lists):""":type lists: List[ListNode]:rtype: ListNode"""def merge2Lists(l1,l2):prehead = point = ListNode(0)while l1 and l2:if l1.val<=l2.val:point.next = l1l1 = l1.nextelse:point.next = l2l2 = l2.nextpoint = point.nextpoint.next = l1 if l1 else l2return prehead.nextif not lists:return Noneamount = len(lists)interval = 1while interval < amount:for i in range(0, amount - interval, interval * 2):lists[i] = merge2Lists(lists[i], lists[i + interval])interval *= 2return lists[0] if amount > 0 else lists

recursion版本divide and conquer

class Solution {
    
public:ListNode* mergeKLists(vector<ListNode*>& lists) {
    return mergek(lists,0,lists.size());}ListNode* mergek(const vector<ListNode*>& lists, const int start, const int end){
    int len = end - start;if(len == 0) return nullptr;if(len == 1) return lists[start];int mid = (start+end) / 2;return merge2Lists(mergek(lists,start,mid),mergek(lists,mid,end));}ListNode* merge2Lists(ListNode* a, ListNode* b){
    if(!a) return b;if(!b) return a;ListNode* dummy = new ListNode(0);ListNode* curr = dummy;while(a && b){
    if(a->val < b->val){
    curr->next = a;a = a->next;curr = curr->next;}else{
    curr->next = b;b = b->next;curr = curr->next;}}if(a) curr->next = a;if(b) curr->next = b;return dummy->next;}
};

二刷解法

divide and conquer内部的逻辑更加的清晰，上面的解法需要考虑end得那个取不取的问题，比较麻烦

class Solution {
    
public:ListNode* divideAndConquer(const vector<ListNode*>& lists, const int start, const int end){
    // cout << start << end << endl;if(start == end){
    return lists[start];}else if(start + 1 == end){
    return mergeTwoLists(lists[start],lists[end]);}else{
    int mid = start + (end-start)/2;return mergeTwoLists(divideAndConquer(lists,start,mid),divideAndConquer(lists,mid+1,end));}}ListNode* mergeTwoLists(ListNode* l1,ListNode* l2){
    ListNode* dummy = new ListNode(-1);ListNode* head = dummy;while(l1 || l2){
    int l1_val = l1 ? l1->val : INT_MAX;int l2_val = l2 ? l2->val : INT_MAX;if(l1_val < l2_val){
    head->next = new ListNode(l1_val);if(l1) l1 = l1->next;}else{
    head->next = new ListNode(l2_val);if(l2) l2 = l2->next;}head = head->next;}return dummy->next;}ListNode* mergeKLists(vector<ListNode*>& lists) {
    if(lists.size() == 0){
    return nullptr;}return divideAndConquer(lists,0,lists.size()-1);}};