每日一题 LCR 078. 合并 K 个升序链表

LCR 078. 合并 K 个升序链表

使用二分法就可以解决

class Solution {
public:ListNode* mergeKLists(vector<ListNode*>& lists) {int n = lists.size();if(n == 0){return nullptr;}ListNode* ans ;ans = binMerge(lists,0,n-1);return ans;}ListNode* binMerge(vector<ListNode*> &lists,int l,int r ){//cout<<l<<" "<<r<<endl;if(l > r){return nullptr;}if(l == r){return lists[l] ;}int mid = (l+r)/2;ListNode* ll = binMerge(lists,l,mid);ListNode* rr = binMerge(lists,mid+1,r);return mergeListTwo(ll,rr);}ListNode* mergeListTwo(ListNode* l, ListNode* r){ListNode* dummy = new ListNode(0);ListNode* h = dummy;while(l && r){if(l->val > r->val){h->next = r;r = r->next;}else{h->next = l;l = l->next;}h = h->next;}if(l){h->next = l;}if(r){h->next = r;}return dummy->next;}
};