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

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
#include <climits>
class Solution {
public:
    ListNode *mergeKLists(vector<ListNode *> &lists) {
        auto head=new ListNode(0);//新建头结点
        auto cur=head;
        int linesNum=lists.size();
        int minNum;
        int minlist;
        while(1)
        {
            minNum=INT_MAX;//由于要找最小值，初始化为最大值
            for(int i=0;i<linesNum;i++)//找最小值
            {
                if(lists[i]!=nullptr&&lists[i]->val<minNum)
                {
                    minNum=lists[i]->val;//记录最小值
                    minlist=i;//记录最小值所在输入链表
                }
            }
            if(minNum==INT_MAX)break; //找不到最小值，即lists内指针都为nullptr，没有剩余
            cur->next=lists[minlist];//最小值加入输出链表
            lists[minlist]=lists[minlist]->next;//最小值去除输入链表
            cur=cur->next;//输出链表后移
        }
        return head->next;
    }
};