{"content":{"title":"Rust每日一题(12)---数据结构-链表--merge-two-sorted-lists","body":"# Rust每日一题(12)---数据结构-链表--merge-two-sorted-lists\r\n[leetcode地址](https:\/\/leetcode.cn\/problems\/merge-two-sorted-lists\/)\r\n将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 \r\n\r\n**示例 1：**\r\n```\r\n输入：l1 = [1,2,4], l2 = [1,3,4]\r\n输出：[1,1,2,3,4,4]\r\n```\r\n**示例 2：**\r\n```\r\n输入：l1 = [], l2 = []\r\n输出：[]\r\n```\r\n\r\n**示例 3：**\r\n```\r\n输入：l1 = [], l2 = [0]\r\n输出：[0]\r\n```\r\n\r\n**难度: 简单**\r\n\r\n## 知识点\r\n- 递归\r\n    - 1.确定终止条件\r\n    - 2.确定初始条件需进行的操作(分)\r\n    - 3.返回待处理结果（治)   \r\n- Match \r\n\r\n## 思路\r\n核心还是分析关键操作步骤，思路出现点是从头到尾分别比较两个链表，哪个链表的数据小，那么就把他设为head，同时将它的next指针设为第二小的元素。此时发现第二小的元素无法确定，因为两个数据后面的元素的深度不知道，此时可以自然反应过来采用递归。\r\n- 终止条件，只有一个数组就直接返回改数据\r\n- 分:将两个list中较小的那个元素的next设置为递归结果的head\r\n- 治:返回该元素作为结果\r\n\r\n```\r\nimpl Solution {\r\n    pub fn merge_two_lists(list1: Option<Box<ListNode>>, list2: Option<Box<ListNode>>) -> Option<Box<ListNode>> {\r\n        match (list1,list2) {\r\n            (Some(p1), None) => Some(p1),\r\n            (None,Some(p2)) => Some(p2),\r\n            (Some(mut p1),Some(mut p2)) => {\r\n                if p1.val > p2.val {\r\n                    let n = p2.next.take();\r\n                    p2.next = Solution::merge_two_lists(Some(p1), n);    \r\n                    Some(p2)\r\n                } else {\r\n                    let n = p1.next.take();\r\n                    p1.next =  Solution::merge_two_lists(n, Some(p2));    \r\n                    Some(p1)\r\n                }\r\n        \r\n            }\r\n            _ => None\r\n        }\r\n    }\r\n}\r\n```"},"author":{"user":"https:\/\/learnblockchain.cn\/people\/720","address":null},"history":null,"timestamp":1662116282,"version":1}