leetcode-23.Merge k Sorted Lists 合并 k 個有序連結清單

題目：

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity. Example: Input: [   1->4->5,   1->3->4,   2->6 ] Output: 1->1->2->3->4->4->5->6

合并 k 個排序連結清單，傳回合并後的排序連結清單。請分析和描述算法的複雜度。 示例: 輸入: [   1->4->5,   1->3->4,   2->6 ] 輸出: 1->1->2->3->4->4->5->6

思路：

（1）可以借鑒合并兩個有序連結清單的思路，比如1,2,3,4,5連結清單，可以1,2合并，然後将結果與3合并。這樣很慢。我們 可以對其二分，再兩兩合并，然後再結合。比如1,2,3,4,5連結清單，我們分别合并（1,2）（3,4）（5）或者我們底下程式采用的這種（1,4）（2,5）（3），這就類似于歸并排序，采用分治法。這樣快很多。 底下的程式k=（n+1）/2表示合并之後總共有幾個表，比如1,2,3,4,5合并一次後有3個表。

/**
 * 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) {
        int n=lists.size(),k;
        if(n==0) return NULL;
        while(n>1)
        {
            k = (n+1)/2;
            for(int i=0;i<n/2;++i)
                lists[i] = mergelist(lists[i],lists[i+k]);
            n=k;
        }
        return lists[0];
    }
    ListNode* mergelist(ListNode* l1,ListNode *l2)//合并倆連結清單
    {
        ListNode* head=new ListNode(-1);
        ListNode* cur = head;
        while(l1 && l2)
        {
            if(l1->val < l2->val)
            {
                cur->next=l1;
                l1=l1->next;
            }else{
                cur->next = l2;
                l2 = l2->next;
            }cur = cur->next;
        }
        if(l1) cur->next = l1;  //記得不要忘了還要連接配接另外一個連結清單
        if(l2) cur->next = l2;
        return head->next;
    }
};
           

（2）用最小堆，首先把k個連結清單的首元素都加入最小堆中，它們會自動排好序。然後我們每次取出最小的那個元素加入我們最終結果的連結清單中，然後把取出元素的下一個元素再加入堆中，下次仍從堆中取出最小的元素做相同的操作，以此類推，直到堆中沒有元素了，此時k個連結清單也合并為了一個連結清單，傳回首節點即可

struct cmp {
    bool operator () (ListNode *a, ListNode *b) {
        return a->val > b->val;
    }
};
class Solution {  
public:  
    ListNode *mergeKLists(vector<ListNode *> &lists) {  
        priority_queue<ListNode*, vector<ListNode*>, cmp> q;
        for (int i = 0; i < lists.size(); ++i) {
            if (lists[i]) q.push(lists[i]);
        }
        ListNode *head = NULL, *pre = NULL, *tmp = NULL;
        while (!q.empty()) {
            tmp = q.top();
            q.pop();
            if (!pre) head = tmp;
            else pre->next = tmp;
            pre = tmp;
            if (tmp->next) q.push(tmp->next);
        }
        return head;
    }  
};
           

參考：http://www.cnblogs.com/grandyang/p/4606710.html