1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126

//! Add Two Numbers [leetcode: add_two_numbers](https://leetcode.com/problems/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.
//! ```
//!
/// # Solutions
///
/// # Approach 1: Elementary Math
///
/// * Time complexity: O(max(m, n))
///
/// * Space complexity: O(max(m, n))
///
/// * Runtime: 4 ms
/// * Memory: 2.3 MB
///
/// ```rust
/// // Definition for singly-linked list.
/// // #[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
/// //     }
/// //   }
/// // }
/// impl Solution {
///     pub fn add_two_numbers(l1: Option<Box<ListNode>>, l2: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
///         let mut dummy1 = l1;
///         let mut dummy2 = l2;
///         let mut root = Some(Box::new(ListNode::new(0)));
///         let mut curr = &mut root;
///         let mut carry = 0;
///
///         while dummy1.is_some() || dummy2.is_some() {
///             match curr {
///                 Some(inner_node) => {
///                     let first = dummy1.take().unwrap_or(Box::new(ListNode::new(0)));
///                     let second = dummy2.take().unwrap_or(Box::new(ListNode::new(0)));
///                     let mut sum = first.val + second.val + carry;
///                     carry = sum / 10;
///                     sum = sum % 10;
///                     inner_node.next.get_or_insert(Box::new(ListNode::new(sum)));
///                     curr = &mut inner_node.next;
///                     dummy1 = first.next;
///                     dummy2 = second.next;
///                 },
///                 None => break,
///             }
///         }
///
///         if carry == 1 {
///             if let Some(node) = curr {
///                 node.next.get_or_insert(Box::new(ListNode::new(1)));
///             }
///         }
///
///         root.unwrap().next
///     }
/// }
/// ```
///
pub fn add_two_numbers(l1: Option<Box<ListNode>>, l2: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
    let mut dummy1 = l1;
    let mut dummy2 = l2;
    let mut root = Some(Box::new(ListNode::new(0)));
    let mut curr = &mut root;
    let mut carry = 0;

    while dummy1.is_some() || dummy2.is_some() {
        match curr {
            Some(inner_node) => {
                let first = dummy1.take().unwrap_or(Box::new(ListNode::new(0)));
                let second = dummy2.take().unwrap_or(Box::new(ListNode::new(0)));
                let mut sum = first.val + second.val + carry;
                carry = sum / 10;
                sum = sum % 10;
                inner_node.next.get_or_insert(Box::new(ListNode::new(sum)));
                curr = &mut inner_node.next;
                dummy1 = first.next;
                dummy2 = second.next;
            },
            None => break,
        }
    }

    if carry == 1 {
        if let Some(node) = curr {
            node.next.get_or_insert(Box::new(ListNode::new(1)));
        }
    }

    root.unwrap().next
}

#[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
    }
  }
}