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

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


class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param lists ListNode类vector 
     * @return ListNode类
     */
     // 直接将所有链表里面的节点放到vec里面，然后排序，再组成链表输出
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        // write code here
     if (lists.empty())
		return nullptr;

	vector<ListNode*> vec;
	for (ListNode *node : lists) // 全部放到vector里
	{
		while (node != nullptr)
		{
			ListNode *tmp = node;
			node = node->next;
			tmp->next = nullptr; // 需要将当前节点的下一个节点置空，否则会无限循环
			vec.push_back(tmp);	
		}
	}

	if (vec.empty())
		return nullptr;
	// 对vector进行排序
	std::sort(vec.begin(), vec.end(), [](ListNode *n1, ListNode *n2) {return n1->val < n2->val; });
	ListNode head(-1);
	ListNode *pHead = &head;
	ListNode *cur = pHead;
	for (ListNode *node : vec) // 重新链接
	{
		cur->next = node;
		cur = cur->next;
		
	}
	return pHead->next;
	}
};