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

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 *	ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
#include <ios>
class Solution {
private:
    vector<ListNode*> lists;
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param lists ListNode类vector 
     * @return ListNode类
     */
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        this->lists = lists;
        int n = lists.size();
        if(n == 0){
            return nullptr;//特殊情况，如果没有任何序列，直接返回空指针
        }
        return mergeTwo(0, n - 1);
        // write code here
    }
    ListNode* mergeTwo(int left, int right){
        if(left == right){
            return lists[left];//返回的条件之一，就是数组不能再划分
        }
        int mid = (right + left) / 2;
        auto lhead = mergeTwo(left, mid);
        auto rhead = mergeTwo(mid + 1, right);//分治法，将链表数组划分为左右两块，假设左右两个链表是两个已经排序完成的链表，因此只需要合并左右两个链表
        if(lhead == nullptr) return rhead;//归并的特殊情况，如果其中一个为空直接返回另一个
        if(rhead == nullptr) return lhead;//归并的特殊情况，如果其中一个为空直接返回另一个
        auto dummy = new ListNode(-1);
        dummy->next = lhead->val > rhead->val ? rhead : lhead;//记录头节点的前驱节点
        auto cur = dummy;//记录生成序列的当前节点
        while(lhead != nullptr && rhead != nullptr){
            
            if(lhead->val > rhead->val){
                cur->next = rhead;
                rhead = rhead->next;
            }else{
                cur->next = lhead;
                lhead = lhead->next;
            }
            cur = cur->next;
        }
        if(lhead != nullptr){
            cur->next = lhead;
        }
        if(rhead != nullptr){
            cur->next = rhead;
        }
        return dummy->next;//返回的条件之二，左右链表已经合并为一个链表
    }
};