C++ O(n*k*log(k)) 48ms solution


  • 0
    A
    class Solution {
    public:
        ListNode* mergeKLists(vector<ListNode*>& lists) {
              if (lists.size() == 0) return nullptr;
    		  // using mycomparison:
    		  typedef priority_queue<ListNode*, std::vector<ListNode*>, cmp> mypq_type;
    		  mypq_type pq;
    		  ListNode* res = new ListNode(0);
    		  ListNode* curr = res;
    		  bool allnull = false;
    		  for (int i = 0; i < lists.size(); ++i){
    		      if (lists[i]) {
    		          pq.emplace(lists[i]);
    		          allnull = true;
    		      }
    		  }
    		  if (!allnull) return nullptr;
    		  while (pq.size()){
    			  ListNode* node = pq.top();
    			  curr->next = new ListNode(node->val);
    			  curr = curr->next;
    			  pq.pop();
    			  if (node->next){pq.push(node->next);}
    		  }
    		  return res->next;
        }
    	
    	struct cmp{
    		bool operator()(const ListNode* lhs, const ListNode* rhs){
    			return lhs->val > rhs->val;
    		}
    	};
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.