2. Add Two Numbers Medium

1/**
2 * [2] Add Two Numbers
3 *
4 * You are given two non-empty linked lists representing two non-negative
5 * integers. The digits are stored in reverse order and each of their nodes
6 * contain a single digit. Add the two numbers and return it as a linked list.
7 *
8 * You may assume the two numbers do not contain any leading zero, except the
9 * number 0 itself.
10 *
11 * Example:
12 *
13 *
14 * Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
15 * Output: 7 -> 0 -> 8
16 * Explanation: 342 + 465 = 807.
17 *
18 */
19pub struct Solution {}
20use crate::util::linked_list::{ListNode};
21
22// problem: https://leetcode.com/problems/add-two-numbers/
23// discuss: https://leetcode.com/problems/add-two-numbers/discuss/?currentPage=1&orderBy=most_votes&query=
24
25// submission codes start here
26
27impl Solution {
28    pub fn add_two_numbers(l1: Option<Box<ListNode>>,l2: Option<Box<ListNode>>,) -> Option<Box<ListNode>> {
29        let (mut l1, mut l2) = (l1, l2);
30        let mut dummy_head = Some(Box::new(ListNode::new(0)));
31        let mut tail = &mut dummy_head;
32        let (mut l1_end, mut l2_end, mut overflow) = (false, false, false);
33        loop {
34            let lhs = match l1 {
35                Some(node) => {
36                    l1 = node.next;
37                    node.val
38                }
39                None => {
40                    l1_end = true;
41                    0
42                }
43            };
44            let rhs = match l2 {
45                Some(node) => {
46                    l2 = node.next;
47                    node.val
48                }
49                None => {
50                    l2_end = true;
51                    0
52                }
53            };
54            // if l1, l2 end and there is not overflow from previous operation, return the result
55            if l1_end && l2_end && !overflow {
56                break dummy_head.unwrap().next;
57            }
58            let sum = lhs + rhs + if overflow { 1 } else { 0 };
59            let sum = if sum >= 10 {
60                overflow = true;
61                sum - 10
62            } else {
63                overflow = false;
64                sum
65            };
66            tail.as_mut().unwrap().next = Some(Box::new(ListNode::new(sum)));
67            tail = &mut tail.as_mut().unwrap().next
68        }
69    }
70}
71
72// submission codes end
73
74#[cfg(test)]
75mod tests {
76    use super::*;
77    use crate::util::linked_list::{to_list};
78
79    #[test]
80    fn test_2() {
81        assert_eq!(
82            Solution::add_two_numbers(to_list(vec![2, 4, 3]), to_list(vec![5, 6, 4])),
83            to_list(vec![7, 0, 8])
84        );
85
86        assert_eq!(
87            Solution::add_two_numbers(to_list(vec![9, 9, 9, 9]), to_list(vec![9, 9, 9, 9, 9, 9])),
88            to_list(vec![8, 9, 9, 9, 0, 0, 1])
89        );
90
91        assert_eq!(
92            Solution::add_two_numbers(to_list(vec![0]), to_list(vec![0])),
93            to_list(vec![0])
94        )
95    }
96}
97