Rust每日一题(12)---数据结构-链表--merge-two-sorted-lists

Rust每日一题(12)---数据结构-链表--merge-two-sorted-lists

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]

难度: 简单

知识点

  • 递归
    • 1.确定终止条件
    • 2.确定初始条件需进行的操作(分)
    • 3.返回待处理结果(治)
  • Match

思路

核心还是分析关键操作步骤,思路出现点是从头到尾分别比较两个链表,哪个链表的数据小,那么就把他设为head,同时将它的next指针设为第二小的元素。此时发现第二小的元素无法确定,因为两个数据后面的元素的深度不知道,此时可以自然反应过来采用递归。

  • 终止条件,只有一个数组就直接返回改数据
  • 分:将两个list中较小的那个元素的next设置为递归结果的head
  • 治:返回该元素作为结果
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
        }
    }
}

本文参与登链社区写作激励计划 ,好文好收益,欢迎正在阅读的你也加入。

  • 发表于 2022-09-02 18:58
  • 阅读 ( 254 )
  • 学分 ( 2 )
  • 分类:Rust

0 条评论

请先 登录 后评论
Johnathan
Johnathan

PhD

24 篇文章, 1335 学分