/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 *	ListNode(int x) : val(x), next(nullptr) {}
 * };
 */

#include <list>
#include <algorithm>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     * 
     * @param lists ListNode类vector 
     * @return ListNode类
     */
    ListNode* mergeKLists(vector<ListNode*>& lists) {
      // 空处理
      if (lists.size() == 0) {
        return nullptr;
      }

      // 创建int类型的顺序表
      vector<int> temp;

      // 将原来n个数据全部插入顺序表中
      for (const auto i : lists) {
        for (auto it = i; it != nullptr; it = it -> next) {
          temp.push_back(it->val);   
        }
      }

      // 对顺序表进行排序
      sort(temp.begin(), temp.end());

      // 创建新链表顺序尾插顺序表中的数据
      lists.push_back(new ListNode(0));
      auto* it = lists[lists.size() - 1];
      for (const auto i : temp) {
        auto* temp = it->next;
        it->next = new ListNode(i);
        it->next->next = temp;
        it = it->next;
      }
      return lists[lists.size() - 1]->next;
    }
};