[InterviewBit] Merge K Sorted Lists

Merge K Sorted Lists

  • Time : O(nlogk)
  • Space : O(k)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
ListNode* Solution::mergeKLists(vector<ListNode*> &A) {
ListNode* dummy = new ListNode(-1);
priority_queue<pair<int,ListNode*>,vector<pair<int,ListNode*>>, greater<pair<int,ListNode*>>> Q;
for(auto& a : A) Q.push({a->val, a});

ListNode* runner = dummy;
while(!Q.empty()) {
auto [_, node] = Q.top(); Q.pop();
runner->next = node;
runner = runner->next;
if(node->next != NULL) Q.push({node->next->val, node->next});
runner->next = NULL;
}

return dummy->next;
}

Author: Song Hayoung
Link: https://songhayoung.github.io/2022/09/05/PS/interviewbit/merge-k-sorted-lists/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.