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

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
// 先完成一个函数，作用是可以将两个升序链表合并成一个升序链表
ListNode* merge(ListNode* x, ListNode* y) {
    ListNode* node = new ListNode(0);
    ListNode* list = node;
    if (x == nullptr || y == nullptr) {
        if (x == nullptr && y == nullptr) {
            return nullptr;
        }
        if (x == nullptr) {
            return y;
        }
        if (y == nullptr) {
            return x;
        }
    }
    while (x != nullptr || y != nullptr) {
        //这里不用对x和y都为nullptr进行判断的原因是总有一方先结束，一起为nullptr不可能
        if (x == nullptr) {
            list->next=y;
            return node->next;
        }
        if (y == nullptr) {
            list->next=x;
            return node->next;
        }
        // 测试函数是否work的时候发现了这个问题，程序运行到这里总是发生段错误
        // 在if里不能光是写判断大小x->val < y->val，因为有可能x或者y经过上面操作后已经有一方是nullptr，然后判断又指向val，那肯定会报错啊！
        // 所以在进行判断时要加上判断它们是否为nullptr的条件，还有一点就是我这里的连接符是&&，只要x或者y为nullptr，即使x->val 或者y->val 是错误的，也不会报错！
        if (x!=nullptr && y!=nullptr&&(x->val < y->val)) {
            ListNode* pnextx = x->next;
            list->next = x;
            x->next = nullptr;
            list = list->next;
            x = pnextx;
        }
        // x!=nullptr && y!=nullptr&&(x->val >= y->val) 正确的
        // (x->val >= y->val)&&x!=nullptr && y!=nullptr 错误的
        // 我人嘛了，没想到if中如果有&&的话，是从左往右执行的，如果左项为false，右项即使有语法错误也不会执行
        // 不过还好当时我故意调整了一下左项与右项的位置，学到了新知识，虽然找bug找了很久（得谢谢自己！）
        if (x!=nullptr && y!=nullptr&&(x->val >= y->val)) {
            ListNode* pnexty = y->next;
            list->next = y;
            y->next = nullptr;
            list = list->next;
            y = pnexty;
        }
    }
    return node->next;
}
class Solution {
  public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        // test function weather works or not!!!
        // ListNode* test=merge(lists[0], lists[1]);
        // while (test!=nullptr) {
        //     cout << test->val << '\t' << endl;
        //     test=test->next;
        // }
        // return test;
        if (lists.size()==0) {
            return nullptr;
        }
        int count=lists.size();
        while (count!=1) {
            lists[lists.size()-2]=merge(lists[lists.size()-1], lists[lists.size()-2]);
            lists.pop_back();
            count=lists.size();
        }
        return lists[0];
    }
};