leetcode/
sum_lists.rs

1//! # 面试题 02.05. 链表求和
2//!
3//! 难度 中等
4//!
5//! 给定两个用链表表示的整数，每个节点包含一个数位。
6//!
7//! 这些数位是反向存放的，也就是个位排在链表首部。
8//!
9//! 编写函数对这两个整数求和，并用链表形式返回结果。
10//!
11//!
12//!
13//! ## 示例：
14//!
15//! ```text
16//! 输入：(7 -> 1 -> 6) + (5 -> 9 -> 2)，即617 + 295
17//! 输出：2 -> 1 -> 9，即912
18//! ```
19//!
20//! 进阶：思考一下，假设这些数位是正向存放的，又该如何解决呢?
21//!
22//! ## 示例：
23//!
24//! ```text
25//! 输入：(6 -> 1 -> 7) + (2 -> 9 -> 5)，即617 + 295
26//! 输出：9 -> 1 -> 2，即912
27//! ```
28//!
29//! See [leetcode](https://leetcode-cn.com/problems/sum-lists-lcci/)
30//!
31use crate::ListNode;
32
33/// 这一题与 [add_two_numbers](super::add_two_numbers) 基本上一样，增加了进阶。
34///
35/// 进阶的问题，先反转链表/栈，再做同样的操作。
36pub struct Solution;
37
38impl Solution {
39    /// 反向链表，即从低位到高位，每位相加，记录进位。
40    pub fn add_two_numbers(l1: Option<Box<ListNode>>, l2: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
41        let mut result = None;
42        let mut tail = &mut result;
43        let mut t = (l1, l2, 0, 0); // (list1, list2, sum, carry)
44        loop {
45            t = match t {
46                (None, None, _, 0) => break,
47                (None, None, _, carry) => (None, None, carry, 0),
48                (Some(list), None, _, carry) | (None, Some(list), _, carry) if list.val + carry >= 10 => {
49                    (list.next, None, list.val + carry - 10, 1)
50                }
51                (Some(list), None, _, carry) | (None, Some(list), _, carry) => {
52                    (list.next, None, list.val + carry, 0)
53                }
54                (Some(l1), Some(l2), _, carry) if l1.val + l2.val + carry >= 10 => {
55                    (l1.next, l2.next, l1.val + l2.val + carry - 10, 1)
56                }
57                (Some(l1), Some(l2), _, carry) => {
58                    (l1.next, l2.next, l1.val + l2.val + carry, 0)
59                }
60            };
61
62            *tail = Some(Box::new(ListNode::new(t.2)));
63            tail = &mut tail.as_mut().unwrap().next;
64        }
65        result
66    }
67
68    /// 进阶，正向链表，用 [`Vec`](Vec) 模拟栈，结果插入新节点时，插入到头部，其它一样
69    ///
70    /// 先把两个链表从高位到低位入栈，出栈的时候就是从低位到高位，可以和上面反向链表一样的处理方式。
71    pub fn add_two_numbers_forward(l1: Option<Box<ListNode>>, l2: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
72        let (mut v1, mut v2) = (vec![], vec![]);
73        let mut lists = (l1, &mut v1, l2, &mut v2);
74        loop {
75            lists = match lists {
76                (None, _, None, _) => break,
77                (Some(n), v, None, v2) | (None, v2, Some(n), v) => {
78                    v.push(n.val);
79                    (n.next, v, None, v2)
80                }
81                (Some(n1), v1, Some(n2), v2) => {
82                    v1.push(n1.val);
83                    v2.push(n2.val);
84                    (n1.next, v1, n2.next, v2)
85                }
86            };
87        }
88
89        let mut result = None;
90        let mut t = (0, 0); // (sum, carry)
91        loop {
92            t = match (v1.pop(), v2.pop(), t.0, t.1) {
93                (None, None, _, 0) => break,
94                (None, None, _, carry) => (carry, 0),
95                (Some(val), None, _, carry) | (None, Some(val), _, carry) if val + carry >= 10 => {
96                    (val + carry - 10, 1)
97                }
98                (Some(val), None, _, carry) | (None, Some(val), _, carry) => {
99                    (val + carry, 0)
100                }
101                (Some(val1), Some(val2), _, carry) if val1 + val2 + carry >= 10 => {
102                    (val1 + val2 + carry - 10, 1)
103                }
104                (Some(val1), Some(val2), _, carry) => {
105                    (val1 + val2 + carry, 0)
106                }
107            };
108
109            result = Some(Box::new(ListNode{
110                val: t.0,
111                next: result,
112            }));
113        }
114        result
115    }
116}
117
118#[cfg(test)]
119mod tests {
120    use super::*;
121
122    #[test]
123    fn test() {
124        let cases = vec![
125            (vec![], (vec![], vec![])),
126            (vec![7,0,8], (vec![7,0,8], vec![])),
127            (vec![7,0,8], (vec![], vec![7,0,8])),
128            (vec![7,0,8], (vec![2,4,3], vec![5,6,4])),
129            (vec![2,1,9], (vec![7,1,6], vec![5,9,2])),
130            (vec![2,1,1,1], (vec![7,1,6], vec![5,9,4])),
131        ];
132
133        for (mut expect, (mut l1, mut l2)) in cases {
134            assert_eq!(expect, ListNode::into_vec(Solution::add_two_numbers(ListNode::from_vec(l1.clone()), ListNode::from_vec(l2.clone()))));
135
136            l1.reverse();
137            l2.reverse();
138            expect.reverse();
139            assert_eq!(expect, ListNode::into_vec(Solution::add_two_numbers_forward(ListNode::from_vec(l1), ListNode::from_vec(l2))));
140        }
141    }
142}
leetcode/sum_lists.rs

leetcode/
sum_lists.rs
