题目:
class Solution {
public:
//合并两个升序链表
ListNode* mergetwo(ListNode* l1, ListNode* l2){
if(!l1 || !l2) return l1 ? l1 : l2;
ListNode* dummy = new ListNode(0);
ListNode* cur = dummy;
while(l1&&l2){
if(l1->val < l2->val){
cur->next = l1;
l1 = l1->next;
}else{
cur->next = l2;
l2 = l2->next;
}
cur = cur->next;
}
cur->next = l1 ? l1 : l2;
return dummy->next;
}
//分治递归合并
ListNode* merge(vector<ListNode*>& lists, int l, int r){
if(l==r) return lists[l]; //只剩一个链表
if(l>r) return nullptr; //传入空链表的情况
int mid = (l+r)/2;
ListNode* left = merge(lists, l, mid); //合并前半部分链表
ListNode* right = merge(lists, mid+1, r); //合并后半部分链表
return mergetwo(left, right);
}
ListNode* mergeKLists(vector<ListNode*>& lists) {
return merge(lists, 0, lists.size()-1);
}
};
声明:本站所有文章,如无特殊说明或标注,均为本站原创发布。任何个人或组织,在未征得本站同意时,禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益,可联系我们进行处理。