解析

我们可以用将所有节点的val和节点地址封装成K-V结构保存进红黑树，val为K，节点为V，这样保存进红黑树里面就会有序了。然后中序遍历红黑树，将所有节点链接起来。红黑树封装的是K-V结构的STL容器有map和multimap这两种，因为考虑到有val重复的节点，所有我们用multimap去存储。

代码

    ListNode *mergeKLists(vector<ListNode *> &lists) 
    {
        multimap<int, ListNode*> mm;  

        // 遍历取出所有链表
        for (int i = 0; i < lists.size(); i++)
        {
            // 遍历当前链表的所有节点
            ListNode* cur = lists[i];
            while (cur)
            {
                // 将节点存入红黑树
                mm.insert(make_pair(cur->val, cur));
                cur = cur->next;
            }
        }
        if (mm.size() == 0)  // 树为空表明没有节点存入，直接返回空
        {
            return nullptr;
        }

        // 遍历红黑树，将所有节点连接起来
        ListNode* head = mm.begin()->second;
        ListNode* tail = nullptr;
        for (auto& pair : mm)
        {
            if (tail)
            {
                tail->next = pair.second;
            }
            tail = pair.second;
        }
        return head;
    }