【算法速刷(10/100)】LeetCode —— 23. 合并 K 个升序链表

按照最朴素的方法，每轮都对所给列表进行一次遍历，O(n)的复杂度获得值最小的节点，并将其上的链表指针后移一位，一旦为空则剔除数组。数组为空时结束循环。

 这样写时间复杂度较高，因为涉及到枚举最小值节点，数组的删除操作，但空间复杂度可以降到O(1)

class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        
        int n = lists.size();

        for(int i = n - 1; i >= 0; i--)
        {
            if(lists[i] == nullptr)
                lists.erase(lists.begin() + i);
        }

        n = lists.size();
        if(n == 0)
            return nullptr;

        ListNode* head = nullptr, *p = nullptr;
        while(lists.size() > 0)
        {
            n = lists.size();

            int minId = 0;
            for(int i = 1; i < n; i++)
            {
                if(lists[i]->val < lists[minId]->val)
                {
                    minId = i;
                }
            }

            if(!head)
            {
                head = p = lists[minId];
            }
            else
            {
                p->next = lists[minId];
                p = p->next;
            }

            lists[minId] = lists[minId]->next;
            if(!lists[minId])
                lists.erase(lists.begin() + minId);
        }

        return head;
    }
};