# 0002. Add Two Numbers

{% tabs %}
{% tab title="❓ Problem Statement" %}

> Source: [LeetCode - Add Two Numbers](https://leetcode.com/problems/add-two-numbers/)\
> GitHub: [Solution / Performance](https://github.com/yylou/leetcode/tree/main/0001-2-sum)

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.
{% endtab %}

{% tab title="✍🏻 Constraints & Example" %}
**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.

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

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

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

{% endtab %}
{% endtabs %}

{% tabs %}
{% tab title="💡 Ideas" %}
{% hint style="info" %}
**Note** that two numbers might have different numbers of digits, so we need to take care of **two linked lists with unequal lengths**.
{% endhint %}

For each iteration, we need to check **whether either l1 or l2 arrives at the end**.
{% endtab %}
{% endtabs %}

{% tabs %}
{% tab title=" 🤖 Python3" %}

```python
class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        cur   = ListNode()
        ret   = cur
        carry = 0
        
        # ==================================================
        #  Linked List + Math                              =
        # ==================================================
        # time  : O(max(n, m))
        # space : O(1)
        
        while l1 or l2:
            if l1: 
                num1 = l1.val
                l1 = l1.next
            else: 
                num1 = 0
                
            if l2: 
                num2 = l2.val
                l2 = l2.next
            else: 
                num2 = 0
            
            val      = num1 + num2 + carry
            carry    = val // 10
            cur.next = ListNode(val % 10)
            cur      = cur.next
        
        # check carry to see if need to create extra node
        if carry != 0: cur.next = ListNode(carry)
            
        return ret.next
```

{% endtab %}

{% tab title="🤖 Java" %}

```java
class Solution {
    /**  
     * @time  : O(max(n, m))
     * @space : O(1)
     */
    
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode cur = new ListNode();
        ListNode ret = cur;
        int carry = 0;
        
        while(l1 != null || l2 != null) {
            int num1, num2;
            
            if(l1 != null) {
                num1 = l1.val;
                l1 = l1.next;
            } else num1 = 0;
            
            if(l2 != null) {
                num2 = l2.val;
                l2 = l2.next;
            } else num2 = 0;
            
            int sum = num1 + num2 + carry;
            carry = sum / 10;
            sum = sum % 10;
            
            cur.next = new ListNode(sum);
            cur = cur.next;
        }
        
        if(carry != 0) cur.next = new ListNode(carry);
        return ret.next;
    }
}


```

{% endtab %}
{% endtabs %}