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

Solution: Find the smallest list-head first using minimum-heap(lgk).

complexity: O(NlgK)

1 /** 2  * Definition for singly-linked list. 3  * struct ListNode { 4  *     int val; 5  *     ListNode *next; 6  *     ListNode(int x) : val(x), next(NULL) {} 7  * }; 8  */ 9 class Solution {10 public:11     class compare {12     public:13         bool operator()(ListNode *a, ListNode *b) {14             return a->val > b->val; // minimum-heap15         }16     };17     18     ListNode *mergeKLists(vector
     
       &lists) {19         priority_queue
      
       , compare> q;20         for(int i = 0; i < lists.size(); i++) {21             if(lists[i]) {22                 q.push(lists[i]);23             }24         }25         ListNode dummy(0), *cur = &dummy;26         while(!q.empty()) {27             ListNode* node = q.top(); q.pop();28             cur->next = node;29             cur = cur->next;30             if(node->next) {31                 q.push(node->next);32             }33         }34         return dummy.next;35     }36 };