题解 | #合并k个已排序的链表#
合并k个已排序的链表
https://www.nowcoder.com/practice/65cfde9e5b9b4cf2b6bafa5f3ef33fa6
/** * struct ListNode { * int val; * struct ListNode *next; * ListNode(int x) : val(x), next(nullptr) {} * }; */ #include <vector> class Solution { public: /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param lists ListNode类vector * @return ListNode类 */ ListNode* mergeKLists(vector<ListNode*>& lists) { // write code here if(lists.size()==1) return lists[0]; ListNode* res=new ListNode(-1); ListNode* cur=res; //暴力法O(n*n) NO //fisrt store in vector then sort then rebuild vector<int> v; for(int i=0;i<lists.size();i++){ while(lists[i]!=nullptr){ v.push_back(lists[i]->val); lists[i]=lists[i]->next; } } sort(v.begin(),v.end()); for(int i=0;i<v.size();i++){ ListNode *node=new ListNode(1); node->val=v[i]; cur->next=node; cur=cur->next; } return res->next; } };
利用vector达到要求
time:O(n)
space:O(n)