[LeetCode]23.Merge k Sorted Lists

【題目】

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

【分析】

無

【代碼】

/*********************************
*   日期：2015-01-06
*   作者：SJF0115
*   題目: 23.Merge k Sorted Lists
*   來源：https://oj.leetcode.com/problems/merge-k-sorted-lists/
*   結果：Time Limit Exceeded
*   來源：LeetCode
*   博客：
**********************************/
#include 
#include 
using namespace std;

struct ListNode{
    int val;
    ListNode *next;
    ListNode(int x):val(x),next(NULL){}
};

class Solution {
public:
    ListNode *mergeKLists(vector &lists) {
        ListNode *head = NULL;
        if(lists.size() == 0){
            return head;
        }//if
        for(int i = 0;i < lists.size();i++){
            head = mergeTwoLists(head,lists[i]);
        }//for
        return head;
    }
private:
    ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) {
        if(l1 == NULL) return l2;
        if(l2 == NULL) return l1;

        if(l1->val < l2->val) {
            l1->next = mergeTwoLists(l1->next, l2);
            return l1;
        } else {
            l2->next = mergeTwoLists(l2->next, l1);
            return l2;
        }
    }
};
// 創建鏈表
ListNode* CreateList(int A[],int n){
    ListNode *head = NULL;
    if(n <= 0){
        return head;
    }//if
    head = new ListNode(A[0]);
    ListNode *p1 = head;
    for(int i = 1;i < n;i++){
        ListNode *node = new ListNode(A[i]);
        p1->next = node;
        p1 = node;
    }//for
    return head;
}

int main() {
    Solution solution;
    vector vecs;
    int A[] = {1,2,4,7,9};
    int B[] = {3,5,8,10,11,12};
    int C[] = {6,10,13};
    int D[] = {15,16,17,23};

    ListNode* head1 = CreateList(A,5);
    ListNode* head2 = CreateList(B,6);
    ListNode* head3 = CreateList(C,3);
    ListNode* head4 = CreateList(D,4);

    vecs.push_back(head1);
    vecs.push_back(head2);
    vecs.push_back(head3);
    vecs.push_back(head4);

    ListNode *head = solution.mergeKLists(vecs);
    // 輸出
    ListNode *p = head;
    while(p){
        cout<val<<" ";
        p = p->next;
    }//while
    cout<

這種方法超時。。。。。。。

【分析二】
采用最小優先級隊列。
第一步：把非空的鏈表裝進最小優先級隊列中。
第二步：遍歷最小優先級隊列，直到最小優先級隊列空為止。每次遍歷，都能從最小優先級隊列中取出具有當前最小的元素的鏈表。
如果除最小元素之外，鏈表不空，重新裝進最小優先級隊列中。
【代碼二】
/*********************************
*   日期：2015-01-06
*   作者：SJF0115
*   題目: 23.Merge k Sorted Lists
*   來源：https://oj.leetcode.com/problems/merge-k-sorted-lists/
*   結果：AC
*   來源：LeetCode
*   博客：
**********************************/
#include 
#include 
using namespace std;

struct ListNode{
    int val;
    ListNode *next;
    ListNode(int x):val(x),next(NULL){}
};

class Solution {
public:
    ListNode *mergeKLists(vector &lists) {
        ListNode *head = new ListNode(-1);
        ListNode *p = head;
        // 最小優先級隊列
        priority_queue,cmp> Heap;
        // 鏈表加入優先級隊列
        for(int i = 0;i < lists.size();i++){
            if(lists[i] != NULL){
                Heap.push(lists[i]);
            }//if
        }//for
        // merge
        while(!Heap.empty()){
            // 最小的
            ListNode *list = Heap.top();
            Heap.pop();
            p->next = list;
            p = list;
            if(list->next != NULL){
                Heap.push(list->next);
            }//if
        }//while
        return head->next;
    }
private:
    // 用於最小優先級隊列
    struct cmp {
        bool operator()(ListNode* node1, ListNode* node2) {
            return node1->val > node2->val;
        }//bool
    };
};
// 創建鏈表
ListNode* CreateList(int A[],int n){
    ListNode *head = NULL;
    if(n <= 0){
        return head;
    }//if
    head = new ListNode(A[0]);
    ListNode *p1 = head;
    for(int i = 1;i < n;i++){
        ListNode *node = new ListNode(A[i]);
        p1->next = node;
        p1 = node;
    }//for
    return head;
}

int main() {
    Solution solution;
    vector vecs;
    int A[] = {1,2,4,7,9};
    int B[] = {3,5,8,10,11,12};
    int C[] = {6,10,13};
    int D[] = {15,16,17,23};

    ListNode* head1 = CreateList(A,5);
    ListNode* head2 = CreateList(B,6);
    ListNode* head3 = CreateList(C,3);
    ListNode* head4 = CreateList(D,4);

    vecs.push_back(head1);
    vecs.push_back(head2);
    vecs.push_back(head3);
    vecs.push_back(head4);

    ListNode *head = solution.mergeKLists(vecs);
    // 輸出
    ListNode *p = head;
    while(p){
        cout<val<<" ";
        p = p->next;
    }//while
    cout<