题解 | #合并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) { // write code here // merge sort if (lists.empty()) return nullptr; return helper(lists,0,lists.size()-1); } ListNode* helper(vector<ListNode*>& lists, int l, int r){ if (l==r) return lists[r]; int mid = l + (r-l)/2; ListNode* left = helper(lists,l,mid); ListNode* right = helper(lists,mid+1,r); return merge(left,right); } ListNode* merge(ListNode* h1, ListNode* h2){ ListNode* root = new ListNode(0), *cur = root; while(h1&&h2){ if(h1->val<h2->val){ cur->next = h1; h1 = h1->next; }else{ cur->next = h2; h2 = h2->next; } cur = cur->next; } // process remaining nodes while(h1){ cur->next = h1; h1 = h1->next; cur = cur->next; } while(h2){ cur->next = h2; h2 = h2->next; cur = cur->next; } return root->next; } };