2020/2/19
题目描述
- 给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。
- 如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。
- 您可以假设除了数字 0 之外，这两个数都不会以 0 开头。
示例
输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807
相关标签
链表
数学
解题思路
-
算法：
我们使用变量来跟踪进位，并从包含最低有效位的表头开始模拟逐位相加的过程。
对两数相加方法的可视化: 342+465=807，每个结点都包含一个数字，并且数字按位逆序存储。
- 复杂度分析
时间复杂度：O(max(m,n))，假设 m 和 n 分别表示 l1 和 l2 的长度，上面的算法最多重复 max(m,n) 次。
空间复杂度：O(max(m,n))， 新列表的长度最多为 max(m,n)+1
源代码
impl Solution {
pub fn add_two_numbers(l1: Option<Box<ListNode>>, l2: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
let mut cf = 0;
let node_val = |x: &Option<Box<ListNode>>| {
if let Some(node) = x {
Some(node.val)
}else {
None
}
};
let mut res: Option<Box<ListNode>> = None;
let (mut p1, mut p2, mut pr) = (&l1, &l2, &mut res);
loop {
let mut sum = 0;
match (node_val(p1), node_val(p2)) {
(Some(val1), Some(val2)) => {
sum = val1 + val2 + cf;
},
(Some(val1), None) => {
sum = val1 + cf;
},
(None, Some(val2)) => {
sum = val2 + cf;
},
(None, None) => {
if cf == 1 {
*pr = Some(Box::new(ListNode::new(1)));
}
break;
},
};
cf = sum / 10;
sum = sum - 10 * cf;
*pr = Some(Box::new(ListNode::new(sum)));
// println!("p1: {:?}, p2: {:?}, pr: {:?}, sum: {}", node_val(p1), node_val(p2), node_val(pr), sum);
if let Some(node) = p1 {
p1 = &node.next;
}
if let Some(node) = p2 {
p2 = &node.next;
}
if let Some(node) = pr {
pr = &mut node.next;
}
}
res
}
}
- 执行用时 : 4 ms, 在所有 Rust 提交中击败了87.57%的用户
- 内存消耗 : 1.9 MB, 在所有 Rust 提交中击败了100.00%的用户
总结
- 在对链表节点进行处理时，可以使用闭包并传入 ref 来减少代码冗余
let node_val = |x: &Option<Box<ListNode>>| {
if let Some(node) = x {
Some(node.val)
}else {
None
}
};
另一种减少代码冗余的方法
p1 = &p1.as_ref().unwrap().next; // 另一种写法，要求p1不为None；
