Merge k Sorted Lists.cpp

/*
Merge k Sorted Lists
====================

You are given an array of k linked-lists lists, each linked-list is sorted in ascending order.
Merge all the linked-lists into one sorted linked-list and return it.

Example 1:
Input: lists = [[1,4,5],[1,3,4],[2,6]]
Output: [1,1,2,3,4,4,5,6]
Explanation: The linked-lists are:
[
  1->4->5,
  1->3->4,
  2->6
]
merging them into one sorted list:
1->1->2->3->4->4->5->6

Example 2:
Input: lists = []
Output: []

Example 3:
Input: lists = [[]]
Output: []

Constraints:
k == lists.length
0 <= k <= 10^4
0 <= lists[i].length <= 500
-10^4 <= lists[i][j] <= 10^4
lists[i] is sorted in ascending order.
The sum of lists[i].length won't exceed 10^4.
*/

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */

class Solution
{
public:
  ListNode *mergeKLists(vector<ListNode *> &lists)
  {
    priority_queue<pair<int, ListNode *>, std::vector<pair<int, ListNode *>>, std::greater<pair<int, ListNode *>>> pq;

    ListNode *dummy = new ListNode(-1);
    auto temp = dummy;

    for (auto &list : lists)
      if (list)
        pq.push({list->val, list});
    while (pq.size())
    {
      auto min = pq.top();
      pq.pop();

      auto newNode = new ListNode(min.second->val);
      temp->next = newNode;
      temp = temp->next;

      if (min.second->next)
        pq.push({min.second->next->val, min.second->next});
    }

    return dummy->next;
  }
};