Rust每日一题(12)---数据结构-链表--merge-two-sorted-lists
leetcode地址 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例 1:
输入:l1 = [1,2,4], l2 = [1,3,4]
输出:[1,1,2,3,4,4]
示例 2:
输入:l1 = [], l2 = []
输出:[]
示例 3:
输入:l1 = [], l2 = [0]
输出:[0]
难度: 简单
核心还是分析关键操作步骤,思路出现点是从头到尾分别比较两个链表,哪个链表的数据小,那么就把他设为head,同时将它的next指针设为第二小的元素。此时发现第二小的元素无法确定,因为两个数据后面的元素的深度不知道,此时可以自然反应过来采用递归。
impl Solution {
pub fn merge_two_lists(list1: Option<Box<ListNode>>, list2: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
match (list1,list2) {
(Some(p1), None) => Some(p1),
(None,Some(p2)) => Some(p2),
(Some(mut p1),Some(mut p2)) => {
if p1.val > p2.val {
let n = p2.next.take();
p2.next = Solution::merge_two_lists(Some(p1), n);
Some(p2)
} else {
let n = p1.next.take();
p1.next = Solution::merge_two_lists(n, Some(p2));
Some(p1)
}
}
_ => None
}
}
}
如果觉得我的文章对您有用,请随意打赏。你的支持将鼓励我继续创作!