一起学Rust-实战leetcode（四）
- 2019 年 10 月 6 日
- 笔记
给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储一位数字。
如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。
您可以假设除了数字 0 之外，这两个数都不会以 0 开头。
示例：
输入：(2 -> 4 -> 3) + (5 -> 6 -> 4) 输出：7 -> 0 -> 8 原因：342 + 465 = 807
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/add-two-numbers
这是来源于leetcode的一道题 “两数相加”，我们使用Rust来实现。
本次实战目的：
了解Rust中 Box<T> 指针在链表中的使用，了解结构体方法，学习 Option<T> 的一些常用方法以及所有权的复习。
简单分析：
按照往常一样，首先对题目进行简单分析，题目给出了两个前提（两个非空链表，除了单个的0，数字开头不会是0），这样可以暂不考虑这道题目的异常情况。
从题目可看出，是将相对应的位置数值相加，同时保持正常的进位，每一个节点都是个位数。每一次的进位如果存在就加到下一个节点的和中。
计算链表：每次循环中将计算并创建的节点，赋值到上一个节点的next。这里会涉及两个引用，一个是整个链表的所有者变量，地址指向的是链表起始的位置，另外一个是对于链表尾部的next的一个可变引用，使用可以将新的节点追加到链表的尾部。
结束：当输入的链表全部遍历结束，并且结尾没有进位的情况下，链表计算完成。
注意：如果出现不等长的输入，空缺的节点需要使用0代替。
本题并不难，例如在PHP中就非常容易实现，比较麻烦的是在Rust中实现会有意想不到的问题，例如所有权的问题等。
下面是题干给出的结构与方法。
#[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, } } }
下面编写一下代码：
fn add_two_numbers(l1: Option<Box<ListNode>>, l2: Option<Box<ListNode>>) -> Option<Box<ListNode>> { // 参数改为可变值 let (mut l1, mut l2) = (l1, l2); // 初始化一个为0的起始节点。 let mut ret = Some(Box::new(ListNode::new(0))); let mut tmp = &mut ret; // 进位值，1或0 let mut up = 0; while l1.is_some() || l2.is_some() || up > 0 { // 获取节点的值，如果没有则为0 let v1 = if let Some(l) = &l1 { l.val } else { 0 }; let v2 = if let Some(l) = &l2 { l.val } else { 0 }; // 计算节点的和需要额外加进位的值 let sum = v1 + v2 + up; // up就是sum/10的整数商 up = sum / 10; let val = Box::new(ListNode::new(sum % 10)); //创建内部可变并获取内部值的next ，赋值为当前计算的节点。 tmp.as_mut().unwrap().next = Some(val); //将可变的next节点指针赋值给尾部变量。 tmp = &mut tmp.as_mut().unwrap().next; // 将节点向下遍历 l1 = if l1.is_some() { l1.unwrap().next } else { None }; l2 = if l2.is_some() { l2.unwrap().next } else { None } } //ret第一个节点是与结果无关的，所以不需要，只需要返回next的值 ret.unwrap().next }
解释：
Box::new(x:T) ，将x值存储到堆内存中，而Box的变量指向此堆内存，对于递归的结构体来说用处非常大，由于结构体需要计算大小，所以通过Box<T>来固定结构体成员的大小，通过指针完成数据的连接。
is_some() ， is_none() 是Option<T>枚举的方法，返回布尔值，是用于判断枚举值是Some(T)还是None值。
unwrap() 是用于获取Some(T)内的值，如果是None则会panic退出，需要注意的是，unwrap会获取调用者的所有权，也就是调用后，调用者变量会失效。与之类似的方法 unwrap_or(def:T) 提供None时的默认值，不会发生panic， unwrap_or_else(f: F) 同样是获取Some内值，并会接受一个处理None情况的函数，函数需要返回与Some内值相同类型的值。这三种方法都会获取调用者的所有权。
as_mut() 将可变的Option<T>枚举引用转换为内部值的可变引用，
Converts from `&mut Option<T>` to `Option<&mut T>`.
as_mut() 需要一个可变的Option引用来调用，并不会转移所有权，并返回一个新的内部可变的Option。
impl 用于定义方法或实现trait，方法中的参数如果不存在self，则需要使用 :: 来调用，如果第一个参数使用 self ， &self ， &mut self 则需要使用点运算符来调用。
