Advertisement
leoanjos

Merge K Sorted Lists

May 20th, 2022
759
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() : val(0), next(nullptr) {}
  7.  *     ListNode(int x) : val(x), next(nullptr) {}
  8.  *     ListNode(int x, ListNode *next) : val(x), next(next) {}
  9.  * };
  10.  */
  11. class Solution {
  12. public:
  13.     ListNode* mergeKLists(vector<ListNode*>& lists) {
  14.         ListNode *head = nullptr, *curr = nullptr;
  15.        
  16.         using Node = pair<int, ListNode*>;
  17.         priority_queue<Node, vector<Node>, greater<Node>> heap;
  18.        
  19.         for (ListNode *node: lists) {
  20.             if (node != nullptr) {
  21.                 heap.emplace(node->val, node);
  22.             }
  23.         }
  24.        
  25.         while (!heap.empty()) {
  26.             ListNode *top = heap.top().second;
  27.             heap.pop();
  28.            
  29.             if (head == nullptr) {
  30.                 head = curr = top;
  31.             } else {
  32.                 curr->next = top;
  33.                 curr = top;
  34.             }
  35.            
  36.             if (top->next != nullptr) {
  37.                 heap.emplace(top->next->val, top->next);
  38.             }
  39.            
  40.             top->next = nullptr;
  41.         }
  42.        
  43.         return head;
  44.     }
  45. };
Advertisement
RAW Paste Data Copied
Advertisement