leetcode_rust/
add_two_numbers.rs

1#![allow(dead_code)]
2
3use crate::linked_list::*;
4
5pub fn add_two_numbers(
6    l1: Option<Box<ListNode>>,
7    l2: Option<Box<ListNode>>,
8) -> Option<Box<ListNode>> {
9    let mut dummy = Box::new(ListNode::new(0));
10    // Secondary pointer
11    let mut cur = &mut dummy;
12    let mut sum = 0;
13
14    let mut l1 = l1.as_ref();
15    let mut l2 = l2.as_ref();
16    while l1.is_some() || l2.is_some() {
17        match l1 {
18            Some(ref node) => {
19                sum += node.val;
20                l1 = l1.unwrap().next.as_ref();
21                // or
22                // l1 = l1.map(|n| n.next.as_ref()).unwrap_or(None);
23            }
24            None => {}
25        }
26
27        match l2 {
28            Some(ref node) => {
29                sum += node.val;
30                l2 = l2.unwrap().next.as_ref();
31            }
32            None => {}
33        }
34
35        cur.next = Some(Box::new(ListNode::new(sum % 10)));
36        sum /= 10;
37        cur = cur.next.as_mut().unwrap();
38    }
39
40    if sum != 0 {
41        cur.next = Some(Box::new(ListNode::new(1)));
42    }
43
44    dummy.next
45}
46
47// add two link lists by transfer them to vector firstly and then transfer them back to lists.
48pub fn add_two_numbers2(
49    l1: Option<Box<ListNode>>,
50    l2: Option<Box<ListNode>>,
51) -> Option<Box<ListNode>> {
52    let vec1 = list_to_vec(l1);
53    let vec2 = list_to_vec(l2);
54    let mut vec3 = vec![];
55    let mut carry = 0;
56    let min_len = vec1.len().min(vec2.len());
57    let max_len = vec1.len().max(vec2.len());
58    for i in 0..min_len {
59        let mut val = vec1[i] + vec2[i] + carry;
60        if val > 9 {
61            val -= 10;
62            vec3.push(val);
63            carry = 1;
64        } else {
65            vec3.push(val);
66            carry = 0;
67        }
68    }
69
70    let rest_vec = if max_len == vec1.len() { vec1 } else { vec2 };
71
72    for i in min_len..max_len {
73        let mut val = rest_vec[i] + carry;
74        if val > 9 {
75            val -= 10;
76            vec3.push(val);
77            carry = 1;
78        } else {
79            vec3.push(val);
80            carry = 0;
81        }
82    }
83
84    if carry == 1 {
85        vec3.push(1);
86    }
87    // The last == 0 and the before of last == 10
88    let last = vec3.len() - 1;
89    if vec3.len() > 1 && vec3[last] == 10 {
90        vec3[last] -= 10;
91        vec3.push(1);
92    }
93    vec_to_list(vec3)
94}
95
96fn list_to_vec(l: Option<Box<ListNode>>) -> Vec<i32> {
97    let mut nums = vec![];
98    let mut list = l;
99    while list.is_some() {
100        match list {
101            Some(ref node) => nums.push(node.val),
102            None => {}
103        };
104        list = list.unwrap().next;
105    }
106    nums
107}
108
109fn vec_to_list(arr: Vec<i32>) -> Option<Box<ListNode>> {
110    let mut head = Box::new(ListNode::new(0));
111
112    let mut cur = &mut head;
113    for num in arr.iter() {
114        cur.next = Some(Box::new(ListNode::new(*num)));
115        cur = cur.next.as_mut().unwrap();
116    }
117
118    head.next
119}
120
121#[cfg(test)]
122mod tests {
123    use super::*;
124
125    #[test]
126    fn test1() {
127        let l1 = Some(Box::new(ListNode {
128            val: 2,
129            next: Some(Box::new(ListNode {
130                val: 4,
131                next: Some(Box::new(ListNode { val: 3, next: None })),
132            })),
133        }));
134        let l2 = Some(Box::new(ListNode {
135            val: 5,
136            next: Some(Box::new(ListNode {
137                val: 6,
138                next: Some(Box::new(ListNode { val: 4, next: None })),
139            })),
140        }));
141        let l3 = Some(Box::new(ListNode {
142            val: 7,
143            next: Some(Box::new(ListNode {
144                val: 0,
145                next: Some(Box::new(ListNode { val: 8, next: None })),
146            })),
147        }));
148
149        assert_eq!(add_two_numbers(l1, l2), l3);
150    }
151
152    #[test]
153    fn test2() {
154        let l1 = Some(Box::new(ListNode {
155            val: 2,
156            next: Some(Box::new(ListNode {
157                val: 4,
158                next: Some(Box::new(ListNode { val: 3, next: None })),
159            })),
160        }));
161        let l2 = Some(Box::new(ListNode {
162            val: 5,
163            next: Some(Box::new(ListNode {
164                val: 6,
165                next: Some(Box::new(ListNode { val: 4, next: None })),
166            })),
167        }));
168        let l3 = Some(Box::new(ListNode {
169            val: 7,
170            next: Some(Box::new(ListNode {
171                val: 0,
172                next: Some(Box::new(ListNode { val: 8, next: None })),
173            })),
174        }));
175
176        assert_eq!(add_two_numbers2(l1, l2), l3);
177    }
178}
leetcode_rust/add_two_numbers.rs

leetcode_rust/
add_two_numbers.rs
