raghuvanshraj

23.cpp

Jul 30th, 2021
657
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  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.     static bool comp(ListNode *a, ListNode *b) {
  12.         return a->val > b->val;
  13.     }
  14.  
  15.     ListNode* mergeKLists(vector<ListNode*> &lists) {
  16.         priority_queue<ListNode*, vector<ListNode*>, function<bool(ListNode*, ListNode*)>> min_heap(comp);
  17.         int k = lists.size();
  18.         for (int i = 0; i < k; ++i) {
  19.             if (lists[i]) {
  20.                 min_heap.push(lists[i]);
  21.             }
  22.         }
  23.        
  24.         if (min_heap.empty()) {
  25.             return NULL;
  26.         }
  27.  
  28.         ListNode *curr = min_heap.top();
  29.         min_heap.pop();
  30.  
  31.         ListNode *res = new ListNode(curr->val);
  32.         ListNode *temp = res;
  33.  
  34.         if (curr->next) {
  35.             min_heap.push(curr->next);
  36.         }
  37.  
  38.         while (not min_heap.empty()) {
  39.             curr = min_heap.top();
  40.             min_heap.pop();
  41.             if (curr->next) {
  42.                 min_heap.push(curr->next);
  43.             }
  44.  
  45.             temp->next = new ListNode(curr->val);
  46.             temp = temp->next;
  47.         }
  48.  
  49.         return res;
  50.     }
  51. };
RAW Paste Data