建设信源网站,导购网站一站式建站,wordpress是模板建站,牛皮纸东莞网站建设技术支持题目来源
23. 合并 K 个升序链表 - 力扣#xff08;LeetCode#xff09; 题目描述 给你一个链表数组#xff0c;每个链表都已经按升序排列。 请你将所有链表合并到一个升序链表中#xff0c;返回合并后的链表。 示例 1#xff1a; 输入#xff1a;lists [[1,4,5],[1,3,…题目来源
23. 合并 K 个升序链表 - 力扣LeetCode 题目描述 给你一个链表数组每个链表都已经按升序排列。 请你将所有链表合并到一个升序链表中返回合并后的链表。 示例 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 题目限制
用最优解做出来 思路分析
在解决给定多个按升序排列的链表将它们合并为一个升序链表的问题时一种常见思路是采用顺序合并。先实现一个能合并两个有序链表的函数通过比较节点值大小依次连接节点来合并。在合并多个链表的主函数里先处理边界情况如链表数组为空或元素全为空链表时直接返回相应结果若有有效链表则先取第一个链表作为初始合并结果随后从第二个链表起循环调用合并两链表的函数不断更新合并结果直至处理完所有链表最终返回合并好的链表头节点其时间复杂度为 O(kn) k为链表个数 n为平均链表长度空间复杂度为 O(1)。 具体代码
/*** 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* mergeTWOLists(ListNode* a,ListNode* b) {ListNode *xtnew ListNode(-1);ListNode *tailxt;while(ab){if(a-valb-val){tail-nexta;aa-next;}else{tail-nextb;bb-next;}tailtail-next;}if(a)tail-nexta;else tail-nextb;return xt-next;}ListNode* mergeKLists(vectorListNode* lists) {if(lists.empty())return nullptr;ListNode *reslists[0];for(int i1;ilists.size();i){if(lists[i])resmergeTWOLists(res,lists[i]);}return res;}
};
这段代码中Solution类里的mergeTwoLists函数用于合并两个有序链表通过创建虚拟头节点利用循环比较两链表当前节点值大小并按需连接循环结束后处理剩余节点最终返回合并后链表头节点mergeKLists函数则是处理多个有序链表的合并先判断链表数组是否为空非空时取首个链表为初始结果再循环调用mergeTwoLists函数依次合并剩余链表最后返回合并好的完整有序链表的头节点整体实现了将多个升序链表合并为一个升序链表的功能。
