IT源码网

合并K个排序链表

itxm 2020年10月21日 编程语言 479 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); 
    } 
};

 

评论关闭
IT源码网

微信公众号号:IT虾米 (左侧二维码扫一扫)欢迎添加!