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

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 *	ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
#include <iterator>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param lists ListNode类vector 
     * @return ListNode类
     */
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        // write code here
        vector<int> p;
        for(auto &list: lists){
            while(list){
                p.push_back(list->val);
                list=list->next;
            }
        }

        sort(p.begin(),p.end());
        ListNode *q= new ListNode(-1);
        ListNode *m=q;
        for(int i=0;i<p.size();i++){
            q->next=new ListNode(p[i]);
            q=q->next;
        }
        return m->next;
    

    }
};

就是将k个链表合并成一个有序链表。首先，我们需要收集所有链表节点，然后按有序的方式放入链表。初始化容器 vector<int> p;

   for(auto &list: lists){
        while(list){
            p.push_back(list->val);
            list=list->next;
        }
    }

这一部分就是把各个链表中的元素都存入vector p中。接下来需要排序。 sort()

然后需要构造一个链表存放有序的元素。new ListNode(-1)初始化头节点。 q指针指向头节点。在遍历有序vector时，每一次创建一个ListNode值为vector对应位置p[i]。然后一个个链接起来。

 for(int i=0;i<p.size();i++){
            q->next=new ListNode(p[i]);
            q=q->next;
        }

最后返回是m->next 跃过头节点。