23. Merge k Sorted Lists

problem description

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

algorithm thought

之前又题目做过合并两个有序链表的，这里是k个。可以借助归并排序的思路，每个两两合并，合并到最后就可以了。也可以用堆的来做。用最小堆，每次从堆中取出最小的链表，然后将这个链表的下一个值重新加入到堆中。在c++中，可以用stl自带的heap类算法做这题，也可以用直接用优先队列来做这题。

我这里是用优先队列来做的

code

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    struct cmp{
        bool operator()(const ListNode* l1,ListNode* l2){
            return l1->val>l2->val;
        }
    };
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        if(lists.size()==0)
            return NULL;
        priority_queue<ListNode*,vector<ListNode*>,cmp> pro;
        for(auto list:lists){
            if(list)
                pro.push(list);
        }
        ListNode* res=new ListNode(-1);
        ListNode* tmp=res;
        while(!pro.empty()){
            tmp->next=pro.top();
            pro.pop();
            tmp=tmp->next;
            if(tmp->next)
                pro.push(tmp->next);
        }
        return res->next;
    }
};

algorithm analysis

这个算法不好分析，现在假设有k个链表，每个链表大小都是n，并且都是一样的链表。首先建堆需要O(k)时间复杂度(我这题不是交换建堆，是一个个插入的)，每次拿出是O(lgk)，再插入是O(lgk)，进行n*k次最后时间是O(n)+O(lgk)*n*k,所以时间复杂度是O(nklgk).当然这只是大致分析。