【题目】

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 <iostream>
#include <vector>
using namespace std;

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

class Solution {
public:
    ListNode *mergeKLists(vector<ListNode *> &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<ListNode*> 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<<p->val<<" ";
        p = p->next;
    }//while
    cout<<endl;
}

【分析二】

采用最小优先级队列。

第一步：把非空的链表装进最小优先级队列中。

第二步：遍历最小优先级队列，直到最小优先级队列空为止。每次遍历，都能从最小优先级队列中取出具有当前最小的元素的链表。

如果除最小元素之外，链表不空，重新装进最小优先级队列中。

【代码二】

/*********************************
*   日期：2015-01-06
*   作者：SJF0115
*   题目: 23.Merge k Sorted Lists
*   来源：https://oj.leetcode.com/problems/merge-k-sorted-lists/
*   结果：AC
*   来源：LeetCode
*   博客：
**********************************/
#include <iostream>
#include <queue>
using namespace std;

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

class Solution {
public:
    ListNode *mergeKLists(vector<ListNode *> &lists) {
        ListNode *head = new ListNode(-1);
        ListNode *p = head;
        // 最小优先级队列
        priority_queue<ListNode*,vector<ListNode*>,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<ListNode*> 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<<p->val<<" ";
        p = p->next;
    }//while
    cout<<endl;
}

[LeetCode]23.Merge k Sorted Lists