合并K个排序链表分析

虾米哥 阅读:362 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); 
    } 
};

 

声明

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

发表评论
搜索
KIKK导航

KIKK导航

排行榜
关注我们

一个IT知识分享的公众号