23. 合并K个排序链表

  大家好，我叫亓官劼（qí guān jié ），在ImapBox中记录学习的点滴历程，时光荏苒，未来可期，加油~博客地址为：亓官劼的博客

本文原创为亓官劼，请大家支持原创，部分平台一直在盗取博主的文章！！！

博主目前仅在ImapBox中写博客，唯一博客更新的地址为：亓官劼的博客

题目

难度 困难

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

示例:

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

题解

  我们之前写过了两个链表的合并，这里K个链表的合并我们只需要顺序的进行两个链表的合并即可。
题解代码为：

/**  * Definition for singly-linked list.  * struct ListNode {  *     int val;  *     ListNode *next;  *     ListNode(int x) : val(x), next(NULL) {}  * };  */ 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* mergeKLists(vector<ListNode*>& lists) {         ListNode *ans = nullptr; for (size_t i = 0; i < lists.size(); ++i) {             ans = mergeTwoLists(ans, lists[i]); } return ans; } }; 

  大家好，我叫亓官劼（qí guān jié ），在ImapBox中记录学习的点滴历程，时光荏苒，未来可期，加油~博客地址为：亓官劼的博客

本文原创为亓官劼，请大家支持原创，部分平台一直在盗取博主的文章！！！

博主目前仅在ImapBox中写博客，唯一博客更新的地址为：亓官劼的博客