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>, l2: Option<Box>) -> Option<Box> {

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

题型与相似题

题型

链表
大数运算

相似题

代码

add_two_numbers