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

/**
 * struct ListNode {
 *  int val;
 *  struct ListNode *next;
 *  ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param lists ListNode类vector
     * @return ListNode类
     */

    ListNode* min(vector<ListNode*>& lists) {
        int min_num = 1001;
        int idx = -1;
        ListNode* temp = new ListNode(0);
        for (struct {vector<ListNode*>::iterator p; int i;} s = {lists.begin(), 0}; s.p
                != lists.end();
                ++(s.p), s.i++) {
            if ((*s.p)->val < min_num) {
                idx = s.i;
                min_num = (*s.p)->val;
            }
        }
        temp->val = lists[idx]->val;
        lists[idx] = lists[idx]->next;
        return temp;
    }


    ListNode* mergeKLists(vector<ListNode*>& lists) {
        // write code here

        lists.erase(std::remove(lists.begin(), lists.end(), nullptr), lists.end());

        int k = lists.size();
        if (k == 0)return nullptr;

        ListNode* res = nullptr;
        ListNode* head = nullptr;


        ListNode* temp;
        while (lists.size()) {
            temp = min(lists);
            if (res == nullptr) {
                res = temp;
                head = res;
            } else {
                head->next = temp;
                head = head->next;
            }
            lists.erase(std::remove(lists.begin(), lists.end(), nullptr), lists.end());

        }


        return res;
    }
};

个人感觉这题并不是很难，因为没有要求空间复杂度，所以可以用一个新的链表去记录合并的排序结果。同时，与合并两个升序链表类似，用k个指针分别沿着k个链表移动，每次移动都选出一个最小值，链接到新链表的末尾。

事实上我上面的代码也没有用到(n)的空间复杂度，因为是在原来的k个链表空间上进行结点的重新链接。

耗费我很多时间的反而是在最开始和每次移动一个指针之后的检查k个链表并删除空链表，因为简单的在原有的链表向量中移除会导致向量的开始和结束位置发生变化，以及索引下标也会改变。最后还是使用<algorithm>库函数remove()来实现的。