image.png
image.png
题目解析
因为是逆序，可以正常的每一个位置对应相加，如果位数不一致，那么缺少的那一个位值为0即可，对应的进位数往前加。
rust 采用 Rust Pattern Matching 写法可以更直观。
https://leetcode.cn/problems/add-two-numbers/solution/rust-pattern-matching-xie-fa-by-anonyuse-kk10/
#[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
}
}
}
/// https://leetcode.cn/problems/add-two-numbers/
pub fn add_two_numbers(l1: Option<Box<ListNode>>, l2: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
let mut result = None;
let mut tail = &mut result;
let mut t = (l1, l2, 0, 0); //(list1, list2, value, carry)
loop {
t = match t {
// 到尾部，退出
(None,None,_,0) => break,
// 如果两个都到底，但是相加还有余
(None,None,_,carry) => (None,None, carry,0),
// 如果某一个到底，并且和余数相加大于等于10
(Some(list), None, _, carry) | (None,Some(list), _, carry) if list.val + carry>=10 => {
(list.next, None, list.val + carry - 10, 1)
},
// 如果某一个到底，并且和余数相加小于10
(Some(list), None, _, carry) | (None,Some(list), _, carry) => {
(list.next, None, list.val + carry, 0)
},
// 如果两个都没到底，并且和余数相加大于等于10
(Some(l1), Some(l2), _, carry) if l1.val + l2.val + carry >=10 => {
(l1.next, l2.next, l1.val + l2.val + carry - 10 , 1)
},
// 如果两个都没到底，并且和余数相加小于10
(Some(l1), Some(l2), _, carry) => {
(l1.next, l2.next, l1.val + l2.val + carry, 0)
},
};
// 赋值
*tail = Some(Box::new(ListNode::new(t.2)));
// 获取下一个节点的引用
tail = &mut tail.as_mut().unwrap().next;
}
result
}
采用递归：
impl Solution {
pub fn add_two_numbers(l1: Option<Box<ListNode>>, l2: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
carried(l1,l2,0)
}
}
pub fn carried(l1: Option<Box<ListNode>>, l2: Option<Box<ListNode>>, mut carry: i32) -> Option<Box<ListNode>> {
if l1.is_none() && l2.is_none() && carry == 0{
None
}else {
Some(Box::new(ListNode{
next: carried(
l1.and_then(|x| {
carry+=x.val;
x.next
}),
l2.and_then(|x| {
carry+=x.val;
x.next
}),
carry / 10
),
val: carry % 10
}))
}
}
复杂度分析
时间复杂度：O(max(m,n))，其中 m 和 n 分别为两个链表的长度。我们要遍历两个链表的全部位置，而处理每个位置只需要 O(1)的时间。
空间复杂度：O(1)。
