一起學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 則需要使用點運算符來調用。
