题解 | #牛群的合并#

考察知识点： 链表

题目分析：

1. 每一次遍历一遍vector,找到指针指向的val最小的那个指针，保存这个指针以及指向这个指针的指针。
2. 通过这个指针将节点插入到新链表末尾，通过指向该指针的指针来使该指针指向下一个结点。
3. 因为每一次遍历都能找到一个要插入到链表中的结点，所以一共需要遍历n次，每次需要查看链表数量(m)的节点。算法复杂度为O(mn)。

所用编程语言： C++

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 *	ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param lists ListNode类vector 
     * @return ListNode类
     */
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        // write code here
        ListNode head(-1);  //创建一个新的结点，使得第一个节点容易插入
        ListNode *p = &head;
        while (true) {
            bool done = true;
            ListNode *m = nullptr;
            ListNode **mp = nullptr;
            int min = 0x3f3f3f3f;
            for (auto &item: lists) {
                if (item == nullptr) continue;
                done = false;
                if (item->val < min) {
                    m = item;
                    min = item->val;
                    mp = &item;
                }
            }
            if (done) break;
            p->next = m;
            p = p->next;
            *mp = (*mp)->next;
        }
        p->next = nullptr;
        return head.next;
    }
};