[ leetcode ] 23. Merge k Sorted Lists

오름 차순으로 연결된 k개의 linked list를 하나의 오름 차순으로 연결된 linked list로 합쳐서 반환하는 문제입니다.

min heap을 구현하여 node들을 heap에 모두 넣고, 하나씩 빼서 모두를 연결하여 반환하였습니다.

queue library를 import하고, struct compare의 operator함수를 overriding하여 min heap을 선언하려 합니다.

struct compare {
    bool operator()(const ListNode* a, const ListNode* b) {
        return a->val > b->val;
    }
};

k개의 linked list를 모두 heap에 넣고, 하나씩 빼면서 prev node와 방금 뺀 node를 연결해주는 방식으로 구현하였습니다.

#include <queue>

/**
 * 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<ListNode*, vector<ListNode*>, compare> pq;
        for (int i = 0; i < lists.size(); i++) {
            ListNode* head = lists[i];
            while (head != NULL) { 
                pq.push(head);
                head = head->next;
            }
        }
        ListNode* answer = NULL;
        ListNode* head = NULL;
        while (!pq.empty()) {
            ListNode* temp = pq.top();
            if (!head) {
                head = temp;
                answer = head;
            }
            else {
                temp->next = NULL;
                head->next = temp;
                head = temp;
            }
            pq.pop();
        }
        return answer;
    }
};