题解 | #合并k个已排序的链表#

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 *	ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
#include <cstddef>
#include <iostream>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param lists ListNode类vector 
     * @return ListNode类
     */
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        // 合并的概念，有k个链表，先将k个头取出，组成一组，循环取最小值，并加入其后面的Node
        vector<ListNode*> listA;
        vector<ListNode*> listB;
        
        ListNode* NodeA = new ListNode(-1);
        ListNode* NodeC = NodeA;
        // 需要先删除空Node
        vector<int> listC;
        for(int i =0;i<lists.size();i++){
            if(lists[i] != nullptr){
                listB.push_back(lists[i]);  
            }
        }
        
        while(listB.size() > 0){
            ListNode* NodeB = listB[0];
            int index = 0;
            // 开始循环查找最小值
            for(int i =0;i<listB.size();i++){
                
                if(listB[i] != nullptr){
                    //cout<<"开始比较："<<NodeB->val<< "," << listB[i]->val <<endl;
                    if(NodeB->val > listB[i]->val){
                        NodeB = listB[i];
                        index = i;
                        //cout<<"有最小值替换"<<NodeB->val<< "," << index <<endl;
                    }
                }
            }
            NodeA->next = NodeB;
            NodeA = NodeA->next;
            // 判断这个ListNode是否已经见底，见底则删除否则换成下一个node
            if(NodeB->next != NULL){
                listB[index] = NodeB->next;
            }else{
                listB.erase(listB.begin() + index);
            }
            //cout<<NodeB->val<< "," <<listB.size()<<endl;
        }
        return NodeC->next;
    }
};