无锡建设公司网站,WordPress支持熊掌号,wordpress 字体类型,2345系统导航题目描述
给你一个链表数组#xff0c;每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中#xff0c;返回合并后的链表。
示例 1#xff1a;
输入#xff1a;lists [[1,4,5],[1,3,4],[2,6]]
输出#xff1a;[1,1,2,3,4,4,5,6]
解释#xff1a;链表数组…题目描述
给你一个链表数组每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中返回合并后的链表。
示例 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.length0 k 10^40 lists[i].length 500-10^4 lists[i][j] 10^4lists[i] 按 升序 排列lists[i].length 的总和不超过 10^4
解答
/*** 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:// 分治合并的方法// 若有k个链表第一轮两两合并得到 k/2 个链表 // 第二轮再两两合并得 k / 4个链表依此类推剩余一个链表然后再自底向上合并ListNode* mergeKLists(vectorListNode* lists) {return merge(lists, 0, lists.size() - 1);}ListNode* mergeKLists1(vectorListNode* lists) {// 顺序合并ListNode *ans nullptr; // 初始和一个空链表合并便于操作for(size_t i 0; i lists.size(); i){ans mergeTwoLists(ans, lists[i]);}return ans;}private:// 将 lists中下标从[l, r]的链表进行合并ListNode *merge(vectorListNode* 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* 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;}};
