合并 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); } };