23. Merge K Sorted Lists

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

Thoughts:

1. Recursively: Divide and Conquer idea: Top down: split K lists into K/2, K/4, ... 2 (or 1), and merge 2 lists, Bottom up: then merging two bigger lists until merging them all.

2. Iteratively:

   1. using Priority Queue, first pushing every listNode in the list, then everytime poping a node from the Priority Queue,

      Checking weather it does have next node, if it does, pushing it into the queue; otherwise, do nothing.

   2. make_heap: use vector as if it is a heap!

Code1:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        if(lists.empty()) return nullptr;
        int len = lists.size();
        while(len > 1){
            for(int i = 0 ; i < len / 2; i++){
                lists[i] = merge2Lists(lists[i], lists[len - 1 - i]);
            }
            len = (len + 1) / 2;
        }

        return lists.front();
    }

    ListNode* merge2Lists(ListNode * l1, ListNode * l2){
        if(!l1) return l2;
        if(!l2) return l1;

        if(l1->val < l2->val){
            l1->next = merge2Lists(l1->next, l2);
            return l1;
        }
        else{
            l2->next = merge2Lists(l1, l2->next);
            return l2;
        }
    }
};

Code 2: using Priority Queue

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    struct compare{
        bool operator()(ListNode* l, ListNode* r){
            return l->val > r-> val;
        }
    };

    ListNode* mergeKLists(vector<ListNode*>& lists) {
        priority_queue<ListNode*, vector<ListNode*>, compare> pq;
        for(auto l : lists){
            if(l) pq.push(l);
        }    
        if(pq.empty()) return nullptr;

        ListNode* answer = pq.top(); pq.pop();
        ListNode* tail = answer;
        if(tail->next) pq.push(tail->next);
        while(!pq.empty()){
            tail->next = pq.top(); pq.pop();
            tail = tail->next;
            if(tail->next) pq.push(tail->next);
        }

        return answer;
    }
};

Code 3: using make_heap

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    static bool heapComp (ListNode * l, ListNode* r){
        return l-> val > r->val;
    }

    ListNode* mergeKLists(vector<ListNode*>& lists) {
        ListNode head(0);
        ListNode* curNode = &head;
        vector<ListNode*> pq;

        for(int i = 0; i < lists.size(); i++){
            if(lists[i]) pq.push_back(lists[i]);
        }
        make_heap(pq.begin(), pq.end(), heapComp);

        while(!pq.empty()){
            curNode -> next = pq.front(); 
            curNode = curNode -> next;
            pop_heap(pq.begin(), pq.end(), heapComp);
            pq.pop_back(); // throw out the least? percolate down?
            if(curNode -> next){
                pq.push_back(curNode->next);
                push_heap(pq.begin(),pq.end(),heapComp); // percolate up?
            }
        }

        return head.next;
    }
};

Special Thanks to ericxiao's solution and mingjun's solution for the reference