Leetcode - 23. Merge k Sorted Lists [H]

문제

오름차순 정렬된 Linked List의 포인터가 k개 담긴 배열이 주어진다. 모든 Linked list의 노드를 오름차순 정렬이 되게 합쳐라.

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

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

해결 아이디어

priority queue 사용. 모든 노드를 min heap에 넣고 pop하면서 리스트를 새로 생성.

실수 한점 → 처음에 priority_queue의 요소를 ListNode *로 했다. 그랬더니 [[-1,-1,-1],[-2,-2,-1]] 예제에서 에러발생. node 포인터 자체를 pq에 넣으니, 각각의 요소에 next 포인터가 존재해서, 뭔가 꼬인듯함.

해결

priority_queue 에 int 값을 넣고, pop하면서 ListNode *를 새로 생성해서 합친다.

class Solution {
public:
    struct compare {
        bool operator()(int a, int b) {
            return a > b;
        }
    };
    ListNode *mergeKLists(vector<ListNode*>& lists) {
        priority_queue<int, vector<int>, compare> pq;
        ListNode *newhead = new ListNode;
        ListNode *node = newhead;
        for (int i = 0; i < lists.size(); i++) {
            while (lists[i]) {
                pq.push(lists[i]->val);
                lists[i] = lists[i]->next;
            }
        }
        while (!pq.empty()) {
            node->next = new ListNode(pq.top());
            node = node->next;
            pq.pop();
        }
        return newhead->next;
    }
};