0002.Add Two Numbers

0002.Add Two Numbers

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Example:

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807.

思路

大数加法的思路,这里只是把存储从数组变成了链表。

从末尾开始加,超过10就进位,主要是注意边界条件,两个链表各自为空的情况

  • 时间复杂度 O(maxlen)
  • 空间复杂度 O(maxlen)

代码

impl Solution {
pub fn add_two_numbers(l1: Option<Box<ListNode>>, l2: Option<Box<ListNode>>) -> Option<Box<ListNode>> {

let (mut l1, mut l2) = (l1,l2);
let mut dummy_head = Some(Box::new(ListNode::new(0)));
let mut tail = &mut dummy_head;
let (mut l1_end, mut l2_end, mut overflow) = (false,false,false);

loop {
let l1_value = match l1 {
Some(node) => { l1 = node.next; node.val},
None => { l1_end = true; 0},
};
let l2_value = match l2 {
Some(node) => { l2 = node.next; node.val},
None => { l2_end = true; 0},
};

if l1_end && l2_end && !overflow {
break dummy_head.unwrap().next
}

let sum = l1_value + l2_value + if overflow { 1 } else { 0 };
let sum = if sum >= 10 { overflow=true; sum -10} else {
overflow=false; sum
};

tail.as_mut().unwrap().next = Some(Box::new(ListNode::new(sum)));
tail = &mut tail.as_mut().unwrap().next
}
}
}
  • 执行用时: 0 ms
  • 内存消耗: 2.1 MB

题型与相似题

题型

  1. 链表
  2. 大数运算

相似题

代码

add_two_numbers

发表评论

Fill in your details below or click an icon to log in:

WordPress.com 徽标

您正在使用您的 WordPress.com 账号评论。 注销 /  更改 )

Google photo

您正在使用您的 Google 账号评论。 注销 /  更改 )

Twitter picture

您正在使用您的 Twitter 账号评论。 注销 /  更改 )

Facebook photo

您正在使用您的 Facebook 账号评论。 注销 /  更改 )

Connecting to %s