Merge k Sorted Lists

단일 링크드리스트의 포인터들이 담긴 벡터를 받는다.

링크드리스트는 노드의 val을 기준으로 오름차순 정렬이 되어있다.

여러 링크드리스트를 오름차순으로 정렬된 하나의 링크드리스트로 병합하여 반환하는 문제

/**
 * 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) {

        auto cmp = [](ListNode* left, ListNode* right) { return left->val > right->val; };
        priority_queue<ListNode*, vector<ListNode*>, decltype(cmp)> pq(cmp);

        for (auto& item : lists)
        {
            if (item != nullptr)
            {
                pq.push(item);
            }
        }

        if (pq.empty())
        {
            return nullptr;
        }
        
        ListNode* head{pq.top()};
        pq.pop();
        ListNode* tail{head};
        
        if (head->next)
        {
            pq.push(head->next);
        }

        ListNode* temp{nullptr};
        while (pq.empty() == false)
        {
            temp = pq.top();
            pq.pop();

            tail->next = temp;
            tail = temp;

            if (temp->next)
            {
                pq.push(temp->next);
            }
        }

        return head;
    }
};