【算法速刷(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;}
};