Leetcode 23: merge k sorted list

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

M1:  merge two sorted list可以通过两个链表的指针进行选择加入哪个节点，对于merge k sorted list，同样可以通过同时比较K个节点，找到最小的节点，然后对当前最小节点的那个链表移动到next指针所指向的node。 如何能够对k个节点直接得到最小的节点呢？？可以用minheap， priority_queue。  
step1: push the initial state into priority_queue
step2: get the  minimal element of the priority_queue, which is the first element in the result list,pop that element out, and push the next element in the current list
step3: iterate do this, until the minheap is empty.

corner case: 1. the list in the lists may be NULL, in this case, no head node to push into the minheap. 2. the next node of cur node may be NULL, no need to push NULL to the min heap.

class comp {
  public:
    bool operator()(ListNode* left, ListNode* right) {
        return left->val > right->val;
    }
};
class Solution {
public:
//use min heap + merge two sorted list method to solve
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        //sanity check
        if (lists.size() == 0 ) return NULL;
        ListNode* dummy = new ListNode(0);
        ListNode* cur =  dummy;
        priority_queue<ListNode*, vector<ListNode*>, comp> minheap;
        //initial state-> get the first minimal element
        for (int i = 0; i < lists.size(); i++) {
            //the list in lists may be NULL
            if (lists[i]) minheap.push(lists[i]);
        }
        while (!minheap.empty()) {
            //get the minimal node
            ListNode* min = minheap.top();
            cur->next = min;
            cur = min;
            minheap.pop();
            if (min->next) minheap.push(min->next);
        }
        return dummy->next;
    }
};

time complexity: O(nk*logK) 因为所有链表中的节点都需要取出来并且push进minheap中，所有时间复杂度是n*k *logk. minheap的大小是k
space complexity: O(k)
M2： 另一种方法在distributed system里面经常用到， server要对多个client里面的数据进行merge，一般用到的就是分治法，类似mergesort进行合并，思想是对于k个sorted list, 如果能够把k/2的sorted list合并好，将另k/2的sorted list 合并好，最后，将合并好的这两个sorted list进行合并，就能得到结果，其实这样做的实质是将链表两个两个地合并，一次遍历合并完，再将新合并好的链表两两合并，最后就可以得到一个合并好的链表。 这个过程可以看做一棵树，树的层数是logk, 每一层需要进行的操作是n*k, 所以时间复杂度和利用minheap的时间复杂度相同，都是O(n*k*logk). 空间复杂度是，如果用递归， 递归栈O（logk），不用递归，空间复杂度为O(1). 其实从时间复杂度和空间复杂度综合分析，分治法的方法更优化。 
以下是不用递归的解法： 1,2,3,4            1&3-》 1 ||  2 &4-》2
class Solution {
private:
//merge two sorted lists
    ListNode* merge(ListNode* l1, ListNode* l2) {
        //sanity check
        if (l1 == NULL && l2 == NULL) return NULL;
        ListNode* dummy = new ListNode(0);
        ListNode* cur = dummy;
        while (l1 && l2) {
            if (l1->val < l2->val) {
                cur->next = l1;
                cur = l1;
                l1 = l1->next;
            }else {
                cur->next = l2;
                cur = l2;
                l2 = l2->next;
            }
        }
        if (l1) cur->next = l1;
        if (l2) cur->next = l2;
        return dummy->next;
    }
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        //sanity check
        if (lists.size() == 0) return NULL;
        int size1 = lists.size();
        while (size1 > 1) {
            int k = (size1 + 1) / 2;
            for (int i = 0; i < size1/2; i++) {
                lists[i] = merge(lists[i], lists[i+k]);
            }
            //the size of the list needed to handle is k
            size1 = k;
        }
        return lists[0];
    }
};