# 2. Leetcode Python: Add Two Numbers - Medium

### 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:**

<figure><img src="/files/qjJRZb0nfo9Ji9mVpP10" alt=""><figcaption></figcaption></figure>

<pre><code><strong>Input: l1 = [2,4,3], l2 = [5,6,4]
</strong><strong>Output: [7,0,8]
</strong><strong>Explanation: 342 + 465 = 807.
</strong></code></pre>

**Example 2:**

<pre><code><strong>Input: l1 = [0], l2 = [0]
</strong><strong>Output: [0]
</strong></code></pre>

**Example 3:**

<pre><code><strong>Input: l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
</strong><strong>Output: [8,9,9,9,0,0,0,1]
</strong></code></pre>

**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.

### Thoughts: <a href="#thoughts" id="thoughts"></a>

1. The first step is instantiating a ListNode class which contains a field for a value and a next pointer. This is used to represent the linked list.&#x20;
2. Then we create a Solution class and make a function that takes two linked lists as input, and outputs the sum of the two numbers.
3. We then initiate a carry flag variable and a current pointer variable that is set to the head of the resulting linked list.&#x20;
4. The next step is to iterate through the two input-linked lists, adding the corresponding values. We store the sum of the two values in a variable named ‘sums’.&#x20;
5. We then find the new node value by taking the modulus 10 of the sum of the two values as this will give us the correct number after accounting for the carry.&#x20;
6. We also find the carrying value by performing integer division by 10.&#x20;
7. We then move the pointers to the next node in each list.&#x20;
8. We then check if we need to create a new node in the linked list. If we need to, we create one and move the current pointer to the new node.&#x20;
9. Finally, we return the output linked list.

### Solution

Time Complexity: O(max(m,n)) \
Space Complexity: O(max(m,n))

```
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution:
    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        #create a carry flag
        carry = 0
        #create the head of the linked list
        curr = output = ListNode(0)
        #iterate through both lists
        while l1 or l2 or carry:
            #add the corresponding values 
            val1 = l1.val if l1 else 0
            val2 = l2.val if l2 else 0
            sums = val1 + val2 + carry
            
            #new node value
            curr.val = sums % 10
            #carry flag
            carry = sums // 10
            
            #move the pointer to the next node 
            l1 = l1.next if l1 else None
            l2 = l2.next if l2 else None
            
            #create the next node if necessary
            if l1 or l2 or carry:
                curr.next = ListNode(0)
                curr = curr.next
                
        return output
            
        
        
def main():
    l1 = ListNode(2, ListNode(4, ListNode(3)))
    l2 = ListNode(5, ListNode(6, ListNode(4, ListNode(10))))
    
    solution = Solution()
    sol1 = solution.addTwoNumbers(l1,l2)
    # print
    while sol1:
        print(sol1.val)
        sol1 = sol1.next if sol1 else None
    

if __name__ == "__main__":
    main()
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://helfipangestu.gitbook.io/leetcode-solutions/solution-1-50/2.-leetcode-python-add-two-numbers-medium.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.