来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/merge-k-sorted-lists
题目描述
给你一个链表数组，每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中，返回合并后的链表。
示例 1： 输入：lists = [[1,4,5],[1,3,4],[2,6]] 输出：[1,1,2,3,4,4,5,6] 解释：链表数组如下： [ 1->4->5, 1->3->4, 2->6 ] 将它们合并到一个有序链表中得到。 1->1->2->3->4->4->5->6 示例 2： 输入：lists = [] 输出：[] 示例 3： 输入：lists = [[]] 输出：[] 提示： k == lists.length 0 <= k <= 10^4 0 <= lists[i].length <= 500 -10^4 <= lists[i][j] <= 10^4 lists[i] 按 升序 排列 lists[i].length 的总和不超过 10^4
解题思路
使用暴力法，每次取最小的链表头，并且更新链表组的数据。时间复杂度为O(k2n)，我们可以维护一个优先队列来代替每次找最小值的过程，这样时间复杂度就可以缩短为O(knlogk)。
同样，我们使用分冶的思路，将链表每次两两合并，由于单次合并的时间复杂度为O(n)，那么时间复杂度也可以达到O(knlogk)。
代码展示
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */ class Solution { public: ListNode* mergeKLists(vector<ListNode*>& lists) { ListNode *pHead = new ListNode(-1); ListNode *pCur = pHead; int iNull = 0; for(auto iter: lists) { if(iter != nullptr) iNull++; } while(iNull) { int iMin = INT_MAX; ListNode* qCur = nullptr; int iIndex = -1; for(int i = 0; i < lists.size(); i++) { if(lists[i]) { if(lists[i]->val < iMin) { qCur = lists[i]; iIndex = i; iMin = lists[i]->val; } } } pCur->next = qCur; lists[iIndex] = qCur->next; if(!lists[iIndex]) iNull--; qCur->next = nullptr; pCur = qCur; } return pHead->next; } };
优先队列方法：
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */ class Solution { public: ListNode* mergeKLists(vector<ListNode*>& lists) { ListNode *pHead = new ListNode(-1); ListNode *pCur = pHead; struct cmp { bool operator() (ListNode *a, ListNode*b) { return a->val > b->val; } }; priority_queue<ListNode*, vector<ListNode*>, cmp> pqueue; for(auto iter: lists) { if(iter) pqueue.push(iter); } while(!pqueue.empty()) { ListNode* qCur = pqueue.top(); pqueue.pop(); pCur->next = qCur; if(qCur->next) pqueue.push(qCur->next); qCur->next = nullptr; pCur = qCur; } return pHead->next; } };
分冶方法：
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */ class Solution { public: ListNode* mergeList(ListNode* p, ListNode*q) { ListNode *pHead = new ListNode(-1); ListNode *pCur = pHead; while(p && q) { if(p->val > q->val) { pCur->next = q; q = q->next; pCur = pCur->next; } else { pCur->next = p; p = p->next; pCur = pCur->next; } } if(p) pCur->next = p; if(q) pCur->next = q; return pHead->next; } ListNode* mergeKLists(vector<ListNode*>& lists) { int iStep = 1; if(lists.size() == 0) return nullptr; while(iStep < lists.size()) { for(int i = 0; i + iStep < lists.size(); i += 2 * iStep) { lists[i] = mergeList(lists[i], lists[i + iStep]); } iStep *= 2; } return lists[0]; } };
运行结果
