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
1 struct cmp { 2 bool operator () (ListNode *a, ListNode *b) { 3 return a->val > b->val; 4 } 5 }; 6 7 class Solution { 8 public: 9 ListNode* mergeKLists(vector<ListNode*>& lists) { 10 ListNode*ans=new ListNode(0); 11 ListNode*head = ans; 12 priority_queue<ListNode*, vector<ListNode*>, cmp>q; 13 for (int i = 0; i < lists.size(); i++) 14 if(lists[i]) 15 q.push(lists[i]); 16 while (!q.empty()) { 17 ListNode* tmp = q.top(); 18 ans->next = tmp; 19 q.pop(); 20 if(tmp->next) 21 q.push(tmp->next); 22 ans = ans->next; 23 } 24 return head->next; 25 } 26 };
看到马上想到的是赢者树败者树，但是太麻烦了
19.1.29 [LeetCode 23] Merge k Sorted Lists
原文：https://www.cnblogs.com/yalphait/p/10335446.html
