LeetCode 23 - Merge k Sorted Lists

题目

Merge k Sorted Lists
[HARD]

Given k sorted linked lists, merge them 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

思路

priority queue (min heap)

代码

class Solution {
public:
    struct compare{
        bool operator()(ListNode* a, ListNode* b){
            return a->val > b->val; // min heap
        }
    };

    ListNode* mergeKLists(vector<ListNode*>& lists) {

        priority_queue<ListNode*, vector<ListNode*>, compare> minHeap;

        // Push all the head nodes of the lists into the min heap
        for (ListNode* list : lists) {
            if (list) {
                minHeap.push(list);
            }
        }

        ListNode dummy(0);
        ListNode* tail = &dummy;

        while (!minHeap.empty()) {
            ListNode* node = minHeap.top();
            minHeap.pop();

            tail->next = node; // Attach the smallest node to the result
            tail = tail->next; // Move the tail pointer

            if (node->next) {
                minHeap.push(node->next); // Push the next node of the current list
            }
        }

        return dummy.next; // Return the merged list starting from the first node  
    }
};