[数据结构与算法]牛客网-NC51 合并k个已排序的链表

一、题目

二、思路

新建vector容器，把所有数据都添加到vector容器中，再利用sort排序，再新构建节点返回

三、代码

新建vector容器，把所有数据都添加到vector容器中，再利用sort排序，再新构建节点返回

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *mergeKLists(vector<ListNode *> &lists) {
        if(lists.empty())
        {
            return nullptr;
        }
        vector<int>res;
        for(int i=0;i<lists.size();++i)
        {
            ListNode *node=lists[i];
            while(node!=nullptr)
            {
                res.emplace_back(node->val);
                node=node->next;
            }
        }
        sort(res.begin(), res.end());
        ListNode *head=new ListNode(res[0]);
        ListNode *pHead=head;
        for(int i=1;i<res.size();++i)
        {
            head->next=new ListNode(res[i]);
            head=head->next;
        }
        return pHead;
    }
};