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
        }
    }
}