题解 | #合并k个已排序的链表#
合并k个已排序的链表
https://www.nowcoder.com/practice/65cfde9e5b9b4cf2b6bafa5f3ef33fa6
/** * 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) { vector<int>record; for(int i=0;i<lists.size();i++) { if(lists[i]==nullptr) { record.push_back(i); } } if(record.size()==lists.size()) { return nullptr; } else { sort(record.begin(), record.end(), greater<>()); for(const auto &it :record) { delete lists[it]; lists.erase(lists.begin() + it); } } int val=lists[0]->val; int num=0; for(int i=0;i<lists.size();i++) { if(lists[i]->val<val) { val=lists[i]->val; num=i; } } auto *q=lists[num]; lists[num]=lists[num]->next; delete q; auto *p=new ListNode(val); p->next=mergeKLists(lists); return p; } };