2. Add Two Numbers

Description of the Problem

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 contains a single digit. Add the two numbers and return the sum as a linked list.

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

Example 1:

Input: l1 = [2,4,3], l2 = [5,6,4]
Output: [7,0,8]
Explanation: 342 + 465 = 807.

Example 2:

Input: l1 = [0], l2 = [0]
Output: [0]

Example 3:

Input: l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
Output: [8,9,9,9,0,0,0,1]

Constraints:

• The number of nodes in each linked list is in the range [1, 100].
• 0 <= Node.val <= 9
• It is guaranteed that the list represents a number that does not have leading zeros.

Solution

Code (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 reverse_list(head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
        let mut curr = head;
        let mut prev = None;

        while let Some(mut node) = curr.take() {
            curr = node.next;
            node.next = prev;
            prev = Some(node);
        }

        return prev;
    }

    pub fn add_two_numbers(l1: Option<Box<ListNode>>, l2: Option<Box<ListNode>>) 
        -> Option<Box<ListNode>> {
        let mut carry : i32 = 0;
        let mut l1 = l1;
        let mut l2 = l2;
        let mut curr = Some(Box::new(ListNode::new(0))); // Dummy head


        while l1.is_some() || l2.is_some() || carry > 0
        {
            let mut sum = carry;
            if let Some(node) = l1 {
                sum += node.val;
                l1 = node.next;
            }

            if let Some(node) = l2 {
                sum += node.val;
                l2 = node.next;
            }

            let mut node = ListNode::new(sum % 10);
            node.next = curr;
            curr = Some(Box::new(node));
            carry = sum / 10;
        }

        curr = Solution::reverse_list(curr);
        
        if let Some(node) = curr {
            curr = node.next;
        }

        return curr;
    }
}

Code (Java)

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode result = new ListNode(0); // Sentinel node
        ListNode current = result;
        int carry = 0;
        while (l1 != null || l2 != null || carry > 0) {
            int sum = carry;
            if (l1 != null){
                sum += l1.val;
                l1 = l1.next;
            }

            if (l2 != null){
                sum += l2.val;
                l2 = l2.next;
            }

            carry = sum / 10;
            current.next = new ListNode(sum % 10);
            current = current.next;
        }
        return result.next;
    }
}

Code (C++)

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode * dummyHead = new ListNode();
        ListNode * curr = dummyHead;
        
        int carry = 0;

        while( l1 != nullptr || l2 != nullptr || carry > 0){
                int val = 
                    (l1 != nullptr ? l1->val : 0) +
                    (l2 != nullptr ? l2->val : 0) +
                    carry;
                carry = val >= 10 ? 1 : 0;
                curr->next = new ListNode( val % 10 );
                
                curr = curr->next;
                l1 = (l1 == nullptr) ? nullptr : l1->next;
                l2 = (l2 == nullptr) ? nullptr : l2->next;
        }
        return dummyHead->next;
    }
};

Complexity (m is the length of list1 and n is the length of list2)

Time complexity:

• \(O(\max(m,n)+1)\)

Auxiliary Space:

• \( O(1) \)