题解 | map缓存池链表合并

1.要按序合并排列k个已排序的链表，首先想到的是取出各个链表的head节点作为一个缓存池pool，并且pool最好也要排序

2.之后从pool中取出最小值，该节点的next节点放入到pool中，pool中各个节点还是要排序，去一个放一个维持pool

3.若某此从pool中取得最小值节点是该链表得tail(next指向nullptr)，说明此链表已经全部取完，那此链表没有节点往pool中放

4.步骤2，3一直迭代，直至pool为空，所有链表已经取完

class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        //初始化multimap,默认是按照键值升序存储
        multimap<int,ListNode*> pool;
        for(int i=0;i<lists.size();i++)
        {
            if(lists[i]==nullptr)
                continue;
            pool.insert(std::pair<int,ListNode*>(lists[i]->val,lists[i]));
        }
        ListNode* res=new ListNode(0);
        ListNode* cur=res;
        while(!pool.empty())
        {
            cur->next=pool.begin()->second;//每次cur会指向pool中最小值节点地址
            cur=cur->next;//cur更新至最小值节点
            //最小值节点next非空节点存入pool中,若为nullptr说明该条链表已取到tail，不再放入pool中
            if(pool.begin()->second->next!=nullptr)
                pool.insert(std::pair<int,ListNode*>(pool.begin()->second->next->val, pool.begin()->second->next));
            pool.erase(pool.begin());//pool中删除当前最小值节点
        }
        return res->next;
    }
};