文章目录
- 23. 合并K个升序链表：
- 样例 1：
- 样例 2：
- 样例 3：
- 提示：
- 分析：
- 题解：
- rust
- go
- c++
- c
- python
- java
23. 合并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 <= 104
- 0 <= lists[i].length <= 500
- -104 <= lists[i][j] <= 104
- lists[i] 按 升序 排列
- lists[i].length 的总和不超过 104
分析：
- 面对这道算法题目，二当家的陷入了沉思。
- 合并有序链表或者合并有序数组非常像归并排序的合并部分。
- 递归和迭代都可以，通常递归更加简单直观，迭代更加高效。
- 可以按顺序合并，但是这样每次只能合并掉一个链表，而用类似归并排序的分治方式则可以每次减少一半数量的链表。
题解：
rust
// Definition for singly-linked list.
// #[derive(PartialEq, Eq, Clone, Debug)]
// pub struct ListNode {
// pub val: i32,
// pub next: Option<Box<ListNode>>
// }
//
// impl ListNode {
// #[inline]
// fn new(val: i32) -> Self {
// ListNode {
// next: None,
// val
// }
// }
// }
impl Solution {
pub fn merge_k_lists(mut lists: Vec<Option<Box<ListNode>>>) -> Option<Box<ListNode>> {
fn merge(lists: &mut Vec<Option<Box<ListNode>>>, l: usize, r: usize) -> Option<Box<ListNode>> {
fn merge_two_lists(list1: Option<Box<ListNode>>, list2: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
match (list1, list2) {
(None, None) => None,
(None, r) => r,
(l, None) => l,
(Some(mut l), Some(mut r)) => {
if l.val <= r.val {
l.next = merge_two_lists(l.next, Some(r));
Some(l)
} else {
r.next = merge_two_lists(Some(l), r.next);
Some(r)
}
}
}
}
if l == r {
return lists[l].take();
}
if l > r {
return None;
}
let mid = (l + r) >> 1;
return merge_two_lists(merge(lists, l, mid), merge(lists, mid + 1, r));
}
let l = lists.len();
if l == 0 {
return None;
}
merge(&mut lists, 0, l - 1)
}
}
go
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func mergeKLists(lists []*ListNode) *ListNode {
var merge func(int, int) *ListNode
merge = func(l int, r int) *ListNode {
var mergeTwoLists func(*ListNode, *ListNode) *ListNode
mergeTwoLists = func(list1 *ListNode, list2 *ListNode) *ListNode {
if nil == list1 {
return list2
}
if nil == list2 {
return list1
}
if list1.Val < list2.Val {
list1.Next = mergeTwoLists(list1.Next, list2)
return list1
} else {
list2.Next = mergeTwoLists(list1, list2.Next)
return list2
}
}
if l == r {
return lists[l]
}
if l > r {
return nil
}
mid := (l + r) >> 1
return mergeTwoLists(merge(l, mid), merge(mid+1, r))
}
return merge(0, len(lists)-1)
}
c++
/**
* 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 {
private:
ListNode *mergeTwoLists(ListNode *list1, ListNode *list2) {
if (!list1) {
return list2;
}
if (!list2) {
return list1;
}
if (list1->val < list2->val) {
list1->next = mergeTwoLists(list1->next, list2);
return list1;
} else {
list2->next = mergeTwoLists(list1, list2->next);
return list2;
}
}
ListNode *merge(vector<ListNode *> &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));
}
public:
ListNode *mergeKLists(vector<ListNode *> &lists) {
return merge(lists, 0, lists.size() - 1);
}
};
c
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode *mergeTwoLists(struct ListNode *list1, struct ListNode *list2) {
if (!list1) {
return list2;
}
if (!list2) {
return list1;
}
if (list1->val < list2->val) {
list1->next = mergeTwoLists(list1->next, list2);
return list1;
} else {
list2->next = mergeTwoLists(list1, list2->next);
return list2;
}
}
struct ListNode *merge(struct 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));
}
struct ListNode *mergeKLists(struct ListNode **lists, int listsSize) {
return merge(lists, 0, listsSize - 1);
}
python
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
def merge(l: int, r: int) -> Optional[ListNode]:
def mergeTwoLists(list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
if list1 is None:
return list2
if list2 is None:
return list1
if list1.val < list2.val:
list1.next = mergeTwoLists(list1.next, list2)
return list1
else:
list2.next = mergeTwoLists(list1, list2.next)
return list2
if l == r:
return lists[l]
if l > r:
return None
mid = (l + r) >> 1
return mergeTwoLists(merge(l, mid), merge(mid + 1, r))
return merge(0, len(lists) - 1)
java
/**
* 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);
}
private 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));
}
private ListNode mergeTwoLists(ListNode list1, ListNode list2) {
if (list1 == null) {
return list2;
}
if (list2 == null) {
return list1;
}
if (list1.val < list2.val) {
list1.next = mergeTwoLists(list1.next, list2);
return list1;
} else {
list2.next = mergeTwoLists(list1, list2.next);
return list2;
}
}
}
非常感谢你阅读本文~
欢迎【点赞】【收藏】【评论】~
放弃不难，但坚持一定很酷~
希望我们大家都能每天进步一点点~
本文由 二当家的白帽子：https://le-yi.blog.csdn.net/ 博客原创~
