合并K个排序链表解析

虾米哥阅读：759 2020-10-21 17:04:42 评论：0

合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。

示例:

输入:
[
1->4->5,
1->3->4,
2->6
]
输出: 1->1->2->3->4->4->5->6

解:这道题一种方法是分治，最小粒度是每两个链表合并

将 kk 个链表配对并将同一对中的链表合并；
第一轮合并以后， kk 个链表被合并成了 \frac{k}{2}
2
k

个链表，平均长度为 \frac{2n}{k}
k
2n

，然后是 \frac{k}{4}
4
k

个链表， \frac{k}{8}
8
k

个链表等等；
重复这一过程，直到我们得到了最终的有序链表。

class Solution { 
public: 
    ListNode* mergeTwoLists(ListNode *a, ListNode *b) { 
        if ((!a) || (!b)) return a ? a : b; 
        ListNode head, *tail = &head, *aPtr = a, *bPtr = b; 
        while (aPtr && bPtr) { 
            if (aPtr->val < bPtr->val) { 
                tail->next = aPtr; aPtr = aPtr->next; 
            } else { 
                tail->next = bPtr; bPtr = bPtr->next; 
            } 
            tail = tail->next; 
        } 
        tail->next = (aPtr ? aPtr : bPtr); 
        return head.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) >> 1; 
        return mergeTwoLists(merge(lists, l, mid), merge(lists, mid + 1, r)); 
    } 
 
    ListNode* mergeKLists(vector<ListNode*>& lists) { 
        return merge(lists, 0, lists.size() - 1); 
    } 
};

标签:加密算法 C++

声明

1.本站遵循行业规范，任何转载的稿件都会明确标注作者和来源；2.本站的原创文章，请转载时务必注明文章作者和来源，不尊重原创的行为我们将追究责任；3.作者投稿可能会经我们编辑修改或补充。