(Leet Code c++)Merge k Sorted Lists

23. Merge k Sorted Lists

Hard

8515382Add to ListShare

You are given an array of k linked-lists lists, each linked-list is sorted in ascending order.

Merge all the linked-lists 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

Example 2:

Input: lists = [] Output: []

Example 3:

Input: lists = [[]] Output: []

 

Constraints:

• k == lists.length
• 0 <= k <= 10^4
• 0 <= lists[i].length <= 500
• -10^4 <= lists[i][j] <= 10^4
• lists[i] is sorted in ascending order.
• The sum of lists[i].length won't exceed 10^4.

주어진 lists의 각 원소들은 모두 오름차순으로 정렬되어 있는 LIstNode다.

이를 모두 합쳐서 연결 리스트로 리턴하면 된다.

 

우선 map을 통해 숫자의 개수를 카운팅한다.

map은 내부적으로 오름차순 정렬된다.

 

정렬된 map을 반복자를 통해 순회한다.

key는 숫자, value는 숫자가 나온 개수(카운팅 수)이기 때문에 value 만큼 key를 answer에 넣어서 이어주면 된다.

/**
 * 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) {
        map<int, int> m;
        ListNode * answer = new ListNode();
        ListNode * tail = answer;
        
        for(int i = 0; i < lists.size(); i++){
            ListNode * head = lists[i];
            
            while(head != NULL){
                m[head->val]++;
                head = head->next;
            }
        }
        
        for(auto itr = m.begin(); itr != m.end(); itr++){
            for(int i = 0; i < itr->second; i++){
                tail->next = new ListNode(itr->first);
                tail = tail->next;
            }
        }
        
        return answer->next;
    }
};