成品网站 售卖,爱设计网,中国企业网站,重庆建站网站建设平台目录 题目描述#xff1a;23. 合并 K 个升序链表#xff08;困难#xff09;题目接口解题思路1代码解题思路2代码 PS: 题目描述#xff1a;23. 合并 K 个升序链表#xff08;困难#xff09;
给你一个链表数组#xff0c;每个链表都已经按升序排列。
请你将所有链表合… 目录 题目描述23. 合并 K 个升序链表困难题目接口解题思路1代码解题思路2代码 PS: 题目描述23. 合并 K 个升序链表困难
给你一个链表数组每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中返回合并后的链表。
LeetCode做题链接LeetCode-合并 K 个升序链表
示例 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题目接口
/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode() {}* ListNode(int val) { this.val val; }* ListNode(int val, ListNode next) { this.val val; this.next next; }* }*/
class Solution {public ListNode mergeKLists(ListNode[] lists) {}
}解题思路1
用一个变量 res 来维护以及合并的链表第 i 次循环把第 i 个链表和 res 合并答案保存到 res 中。
代码
/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode() {}* ListNode(int val) { this.val val; }* ListNode(int val, ListNode next) { this.val val; this.next next; }* }*/
class Solution {public ListNode mergeKLists(ListNode[] lists) {if (lists null || lists.length 0) {return null;}ListNode res lists[0];for (int i 1; i lists.length; i) {if (lists[i] null) {continue;}res mergeTwoLists(res, lists[i]);}return res;}private ListNode mergeTwoLists(ListNode res, ListNode list) {if (res null) {return list;} else if (list null) {return res;} else if (res.val list.val) {res.next mergeTwoLists(res.next, list);return res;} else {list.next mergeTwoLists(res, list.next);return list;}}
}成功
解题思路2
可以两两有序合并的方式然后重复两两有序合并的过程最后得到一个有序的链表
代码
/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode() {}* ListNode(int val) { this.val val; }* ListNode(int val, ListNode next) { this.val val; this.next next; }* }*/
class Solution {public ListNode mergeKLists(ListNode[] lists) {return merge(lists, 0, lists.length - 1);}public ListNode merge(ListNode[] lists, int l, int r) {if (l r) {return lists[l];}if (l r) {return null;}int mid (l r) 1;return mergeTwoLists(merge(lists, l, mid), merge(lists, mid 1, r));}public ListNode mergeTwoLists(ListNode a, ListNode b) {if (a null || b null) {return a ! null ? a : b;}ListNode head new ListNode(0);ListNode tail head, aPtr a, bPtr b;while (aPtr ! null bPtr ! null) {if (aPtr.val bPtr.val) {tail.next aPtr;aPtr aPtr.next;} else {tail.next bPtr;bPtr bPtr.next;}tail tail.next;}tail.next (aPtr ! null ? aPtr : bPtr);return head.next;}
}成功
PS:
感谢您的阅读如果您觉得本篇文章对您有所帮助请给予博主一个赞喔~
