leetcode/
add_two_numbers.rs

1//! # 2. 两数相加
2//!
3//! 难度 中等
4//!
5//! 给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。
6//!
7//! 如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。
8//!
9//! 您可以假设除了数字 0 之外，这两个数都不会以 0 开头。
10//!
11//! ## 示例：
12//!
13//! ```text
14//! 输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
15//! 输出：7 -> 0 -> 8
16//! 原因：342 + 465 = 807
17//! ```
18//!
19//! See [leetcode](https://leetcode-cn.com/problems/add-two-numbers/)
20use crate::ListNode;
21
22/// 这一题与 [sum_lists](super::sum_lists) 基本上一样，除了进阶。
23pub struct Solution;
24
25impl Solution {
26    pub fn add_two_numbers(l1: Option<Box<ListNode>>, l2: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
27        let mut result = None;
28        let mut tail = &mut result;
29        let mut t = (l1, l2, 0, 0); // (list1, list2, sum, carry)
30        loop {
31            t = match t {
32                (None, None, _, 0) => break,
33                (None, None, _, carry) => (None, None, carry, 0),
34                (Some(list), None, _, carry) | (None, Some(list), _, carry) if list.val + carry >= 10 => {
35                    (list.next, None, list.val + carry - 10, 1)
36                }
37                (Some(list), None, _, carry) | (None, Some(list), _, carry) => {
38                    (list.next, None, list.val + carry, 0)
39                }
40                (Some(l1), Some(l2), _, carry) if l1.val + l2.val + carry >= 10 => {
41                    (l1.next, l2.next, l1.val + l2.val + carry - 10, 1)
42                }
43                (Some(l1), Some(l2), _, carry) => {
44                    (l1.next, l2.next, l1.val + l2.val + carry, 0)
45                }
46            };
47
48            *tail = Some(Box::new(ListNode::new(t.2)));
49            tail = &mut tail.as_mut().unwrap().next;
50        }
51        result
52    }
53}
54
55#[cfg(test)]
56mod tests {
57    use super::*;
58    use crate::list;
59
60    #[test]
61    fn test() {
62        let cases = vec![
63            (vec![], (list![], list![])),
64            (vec![7,0,8], (list![7,0,8], list![])),
65            (vec![7,0,8], (list![], list![7,0,8])),
66            (vec![7,0,8], (list![2,4,3], list![5,6,4])),
67            (vec![2,1,9], (list![7,1,6], list![5,9,2])),
68            (vec![2,1,1,1], (list![7,1,6], list![5,9,4])),
69        ];
70
71        for (expect, (l1, l2)) in cases {
72            assert_eq!(expect, ListNode::into_vec(Solution::add_two_numbers(l1, l2)));
73        }
74    }
75}
leetcode/add_two_numbers.rs

leetcode/
add_two_numbers.rs
