[LeetCode] C++ 23. Merge k Sorted Lists.

https://leetcode.com/problems/merge-k-sorted-lists/

 

문제

 

문제 분석

- priority queue를 이용해서 정리한 뒤, 요소를 하나씩 빼서 연결시키면 됩니다.

- 어떤 방식으로든지 정렬을 해서 하나씩 뽑아서 넣으면 됩니다.

 

풀이

class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        if (lists.empty()){
            return nullptr;
        }

        auto compare = [](ListNode* a, ListNode* b){
            return a->val > b->val;
        };

        std::priority_queue<ListNode*, std::vector<ListNode*>, decltype(compare)> pq(compare);

        for(ListNode* list: lists){
            if (list != nullptr){
                pq.push(list);
            }
        }

        ListNode dummy;
        ListNode* tail = &dummy;

        while(!pq.empty()){
            ListNode* smallest = pq.top();
            pq.pop();

            tail->next = smallest;
            tail = tail->next;

            if (smallest->next != nullptr){
                pq.push(smallest->next);
            }
        }

        return dummy.next;
    }
};