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

这里的k个链表都存储在了vector中。
核心思想是依次取出vector的末尾两个链表，将其pop_back。
之后再将其递增合并 push_back 回vector
直到最后vector只剩一个链表，最后return lists[0]

class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param lists ListNode类vector
     * @return ListNode类
     */

    ListNode* Merge(ListNode* p1, ListNode* p2) { // 合并两个链表
        if(p1==nullptr) // 健壮性
            return p2;
        if(p2==nullptr) 
            return p1;
        ListNode* head = nullptr;  // 合并之后链表的起始节点
        ListNode* p = head; // 用p指针记录合并 好之后的链表 的最后一个元素（因为相当于尾插）
        while (p1 != nullptr && p2 != nullptr) {
            if (p1->val <= p2->val) { // 哪个小，就把它尾插到p的后面
                if (head == nullptr)  // 第一次，更新head值
                {
                    ListNode* t = p1->next;
                    head = p1;
                    p = head;
                    p1 = t;
                    p->next=nullptr; // 断开
                }
                else
                {
                    ListNode* t = p1->next;
                    p1->next = p->next;
                    p->next = p1;
                    p1 = t;
                    p=p->next; // 更新p值
                }
            } 
            else {
                if (head == nullptr)
                {
                    ListNode* t = p2->next;
                    head = p2;
                    p = head;
                    p2 = t;
                    p->next=nullptr;
                }
                else 
                {
                    ListNode* t = p2->next;
                    p2->next = p->next;
                    p->next = p2;
                    p2 = t;
                    p=p->next;
                }
            }
        }
        if(p1!=nullptr)
        {
            p->next=p1;
        }
        if(p2!=nullptr)
        {
            p->next=p2;
        }
        return head;
            
    }

    ListNode* mergeKLists(vector<ListNode*>& lists) {
        // write code here
        if(lists.size()==0) // 如果为0，则没有必要进行处理
            return nullptr;

        int k = lists.size(); // 记录有多少个链表
        while (k > 1) {
            ListNode* p = Merge(lists[k - 1], lists[k-2]);  // p为合并好的
            lists.pop_back(); 
            lists.pop_back(); // 删除 
            lists.push_back(p); // 插入
            k--; // 更新k值
        }
        return lists[0];

    }
};