[LinkedList][Hard] 23. Merge k Sorted Lists

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

 

다수의 정렬된 list가 주어질 때, 모든 정렬을 유지하면서 이 list를 하나로 merge 하라.

 

정렬이 되어 있으므로, 각 list의 제일 앞 node를 비교하며 제일 작은 순서대로 

새 노드에 연결하면 될 것이다. 

 

매번 모든 앞 노드를 비교하면서 최소 값을 가진 노드를 찾을 수 있고, 이것은 시간이 많이 걸릴 것이다. 

혹은 추가되는 노드만 더하면서 정렬할 수도 있겠다. 

map 이나 priority queue를 사용하면 될 것 같다. 

 

코드

 

void pushNode(map<int, vector<ListNode*>>& mNodes, ListNode* target)
{
    if (mNodes.find(target->val) == mNodes.end())
    {
        vector<ListNode*> vBuff{ target };
        mNodes[target->val] = vBuff;
    }
    else mNodes[target->val].push_back(target);
}

ListNode* mergeKLists(vector<ListNode*>& lists) 
{
    map<int, vector<ListNode*>> mNodes;
    for (int q = 0; q < lists.size(); ++q)
    {
        if (lists[q] != nullptr)
            pushNode(mNodes, lists[q]);
    }

    ListNode* head = nullptr;
    ListNode* prev = nullptr;
    while (mNodes.size() > 0)
    {
        auto iter = mNodes.begin();
        ListNode* node = iter->second[ iter->second.size() - 1];
        iter->second.pop_back();
        if (iter->second.size() == 0)
            mNodes.erase(iter->first);

        if (head == nullptr)	head = node;
        if (prev != nullptr)	prev->next = node;

        prev = node;

        if (node->next != nullptr)
            pushNode(mNodes, node->next);
    }
    return head;
}

 

 

결과

 

 

정렬(혹은 그에 상응하는 자료구조) + linkedList의 복합 문제.

좋은 문제다.