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. 大数运算

相似题

• 415. Add Strings
• 43. Multiply Strings
• 371. Sum of Two Integers

代码

add_two_numbers