1
2
3

输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94

// @lc code=start
// Definition for singly-linked list.
// #[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
//     }
//   }
// }
impl Solution {
    /// ## 解题思路
    /// 1. 新建一个空链表d；
    /// 2. 依次从头取出l1,l2的各个节点，计算对应节点数字和；
    /// 3. 根据和及是否进位生产结果节点，append到链表d末尾；
    /// 4. 当l1,l2所有节点遍历完，且进位数也为0时，结束遍历；
    pub fn add_two_numbers(
        l1: Option<Box<ListNode>>,
        l2: Option<Box<ListNode>>,
    ) -> Option<Box<ListNode>> {
        match (l1, l2) {
            (None, None) => None,
            (Some(n), None) | (None, Some(n)) => Some(n),
            (Some(n1), Some(n2)) => {
                let sum = n1.val + n2.val;
                if sum < 10 {
                    Some(Box::new(ListNode {
                        val: sum,
                        next: Solution::add_two_numbers(n1.next, n2.next),
                    }))
                } else {
                    let carry = Some(Box::new(ListNode::new(1)));
                    Some(Box::new(ListNode {
                        val: sum - 10,
                        next: Solution::add_two_numbers(
                            carry,
                            Solution::add_two_numbers(n1.next, n2.next),
                        ),
                    }))
                }
            }
        }

        /*         let (mut l1, mut l2) = (l1, l2);
        let mut dummy_head = Some(Box::new(ListNode::new(0)));
        let mut tail = &mut dummy_head;
        let (mut l1_end, mut l2_end, mut overflow) = (false, false, 0_i32);
        let result = loop {
            let val1 = match l1 {
                Some(node) => {
                    l1 = node.next;
                    node.val
                }
                None => {
                    l1_end = true;
                    0
                }
            };
            let val2 = match l2 {
                Some(node) => {
                    l2 = node.next;
                    node.val
                }
                None => {
                    l2_end = true;
                    0
                }
            };
            // 如果l1,l2都结束，且进位标志也为0，则跳出loop
            if l1_end && l2_end && overflow == 0 {
                break dummy_head.unwrap().next;
            }
            // 否则计算当前节点和进位值
            let sum = val1 + val2 + overflow;
            overflow = if sum > 9 { 1 } else { 0 };
            let sum = sum % 10;

            // 将sum节点append 新链表尾部
            tail.as_mut().unwrap().next = Some(Box::new(ListNode::new(sum)));
            // 移动尾指针
            tail = &mut tail.as_mut().unwrap().next;
        };

        result */
    }
}
// @lc code=end

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution:
    '''
    ## 解题思路
    1. 同时遍历l1, l2;
    2. 设置额外的两个变量p, a，分别记录遍历过程中计算的链表头和进位数；
    3. 将遍历中每个l1,l2的val相加，根据和计算进位和当前值，生成新node,加入到p尾部；
    4. 处理将剩余链表；
    '''
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        p = dummy = ListNode(0)
        a = 0  #进位
        while l1 is not None or l2 is not None:
            v = a + (l1.val if l1 is not None else 0) + (l2.val if l2 is not None else 0)
            a = int(v/10)
            v = v - a*10
            p.next = ListNode(v)
            p = p.next
            l1 = l1.next if l1 is not None else None
            l2 = l2.next if l2 is not None else None

        if a > 0:
            p.next = ListNode(a)

        return dummy.next