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

思路讲一下, 由于这个题目很坑爹, 时间复杂度要达到nlogn, 那么意味着我们不能用双循环, 就很恶心, 所以我们分解题目步骤, 思路如下:

1. 先让列表全部串起来, 形成一个未排序的大链表
2. 然后把链表排个序, 返回头结点即可

注意要点

1. 由于牛客网给的输入并不是C++标准库里的链表list而是指针, 那么我们需要自己手动给链表排序
2. 排序算法有很多, 但是冒泡等排序方法复杂度太高, 我们选择插入的时候自动按顺序排序, 这样复杂度就只有O(n)
3. 方法的话可以用C++标准库里的multiset, 他可以给每个元素排序且每个数值可以存放多个, 避免冲突问题, 全部插入完成后再挨个赋值回去就行了
4. 注意处理全空容器和只含有空链表的容器, 两个概念是不一样的比如前者是[], 后者是[{},{}]这样的

本人代码写的很丑, 也没采用模块化设计, 如果看不懂我代码的欢迎留言. 希望各位看官老爷不要嫌弃

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
  public:




    ListNode* mergeKLists(vector<ListNode*>& lists) {
        if (lists.empty() == true) {//如果是空就返回空
            return NULL;
        }
        ListNode* temp, *initList;
        vector<ListNode*> endList;//endList代表一个临时用于操作lists的相同的vector(容器, 也就是存放多链表的东西), 等于说我们复制一份进行瞎搞操作, 不会影响原有的容器
        
        int counterNb = 0;//计数器, 用于计数和计算链表或者容器长度/容量
        
        
        for (vector<ListNode*>::iterator it = lists.begin(); it != lists.end(); it++) {//采用迭代器,把空链表全部删除
            if (*it == NULL) {
                it = lists.erase(it);
                it--;
            }
        }
        if (lists.empty() == true) {//删完以后如果是空vector(容器, 也就是存放多链表的东西), 则直接返回空
            return NULL;
        }

        endList = lists;//进行复制lists操作
        temp = endList[0];//让temp指针指向容器的第一个节点作为头结点, 等一下可以移动temp来达成我们想要的操作
        initList = temp;//专门搞个头结点指针用于记录
        counterNb = 0;//初始化计数器, 此时计数器用来操作第x个链表
        while (endList[counterNb] != NULL) {//由于条件太苛刻, 我们这一轮负责把每个链表都串起来
            if (endList[counterNb]->next != NULL) {
                endList[counterNb] = endList[counterNb]->next;//对于单个链表来说, 如果下个节点不为空则移动到下个节点
            } else {//下个节点为空
                if (counterNb < lists.size() - 1) {//如果没到最后一个链表
                    endList[counterNb]->next = endList[counterNb + 1];//那么我们就让他指向下一个链表的头结点
                    endList[counterNb] = endList[counterNb]->next;//移动到下一个节点
                    counterNb++;
                } else {//到了最后一个链表也让他进入下一个节点-空节点, 用于跳出循环
                    endList[counterNb] = endList[counterNb]->next;//移动到下一个节点
                }
            }


        }
        temp = initList;//临时指针恢复到头结点位置
        counterNb = 0;//初始化计数器, 此时用来计算链表长度, 其实不需要, 因为我们可以用C++标准库里的迭代器
        while (temp != NULL) {
            temp = temp->next;
            counterNb++;
        }
        temp = initList;//临时指针恢复到头结点位置
        multiset<int> tempSet;//直接使用multiset可以帮忙排序, 也兼容多个重复的值
        for (int i = 0; i < counterNb; i++) {//把值全部插入到multiset中, 它会自动帮我们升序排序
            tempSet.insert(temp->val);
            temp = temp->next;
        }
        temp = initList;//临时指针恢复到头结点位置 
        for (multiset<int>::iterator it = tempSet.begin(); it != tempSet.end(); it++) {
            temp->val = *it;//挨个重新覆写数值到原有的链表
            temp = temp->next;
        }


        return initList;//把头结点传回去就好啦

    }
};