# LeetCode 445: Add Two Numbers II

## Problem Restatement

We are given two non-empty linked lists.

Each linked list represents a non-negative integer.

Each node stores one digit, and the digits are stored in forward order. That means the most significant digit comes first.

For example:

```python
7 -> 2 -> 4 -> 3
```

represents:

```python
7243
```

We need to add the two numbers and return the sum as a linked list, also in forward order.

The numbers have no leading zero, except for the number `0` itself. The official problem asks us to return the sum as a linked list with the most significant digit first.

## Input and Output

| Item | Meaning |
|---|---|
| Input | Two linked lists `l1` and `l2` |
| Output | A linked list representing their sum |
| Digit order | Most significant digit first |
| Node value | A single digit from `0` to `9` |
| Leading zeros | Not present, except the number `0` |

The node class is usually:

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

## Examples

Example 1:

```python
l1 = [7, 2, 4, 3]
l2 = [5, 6, 4]
```

These represent:

```python
7243 + 564 = 7807
```

So the output is:

```python
[7, 8, 0, 7]
```

Example 2:

```python
l1 = [2, 4, 3]
l2 = [5, 6, 4]
```

These represent:

```python
243 + 564 = 807
```

Output:

```python
[8, 0, 7]
```

Example 3:

```python
l1 = [0]
l2 = [0]
```

Output:

```python
[0]
```

## First Thought: Reverse the Lists

If the digits were stored backward, addition would be easy.

We could start from the ones place, add digit by digit, and carry as needed.

But here the lists begin with the largest place value.

One option is:

1. Reverse both input lists.
2. Add them normally.
3. Reverse the result.

This works, but it modifies the input lists unless we carefully copy them first.

A cleaner solution is to use stacks.

## Key Insight

A stack lets us read the linked list from left to right, then process it from right to left.

For example:

```python
l1 = 7 -> 2 -> 4 -> 3
```

After pushing values into a stack:

```python
[7, 2, 4, 3]
```

Popping gives:

```python
3, 4, 2, 7
```

That is exactly the order needed for manual addition.

We use two stacks:

| Stack | Stores |
|---|---|
| `stack1` | Digits from `l1` |
| `stack2` | Digits from `l2` |

Then we repeatedly pop digits, add them with carry, and build the result by inserting each new digit at the front.

## Algorithm

Push all digits from `l1` into `stack1`.

Push all digits from `l2` into `stack2`.

Initialize:

```python
carry = 0
head = None
```

While either stack still has digits, or `carry` is non-zero:

1. Start with `total = carry`.
2. If `stack1` is not empty, pop and add its top digit.
3. If `stack2` is not empty, pop and add its top digit.
4. The new digit is:

```python
total % 10
```

5. The new carry is:

```python
total // 10
```

6. Create a new node for the digit.
7. Insert it before the current result head.

Return `head`.

## Correctness

The stacks store the digits of each input number in reverse processing order. Therefore, each pop gives the next digit from least significant to most significant.

At each step, the algorithm adds the current digit from `l1`, the current digit from `l2`, and the carry from the previous lower-place addition. This is exactly the standard column addition rule.

The digit stored in the result node is `total % 10`, which is the correct digit for the current place. The carry becomes `total // 10`, which is the amount that must be added to the next higher place.

Because we process digits from least significant to most significant, each new result digit belongs before the already-built result list. Inserting each new node at the front keeps the final linked list in forward order.

When both stacks are empty and carry is zero, all digits and carries have been processed. The returned list therefore represents the exact sum of the two input numbers.

## Complexity

| Metric | Value | Why |
|---|---:|---|
| Time | `O(m + n)` | Each input node is pushed and popped once |
| Space | `O(m + n)` | The stacks store all input digits |

Here, `m` and `n` are the lengths of the two linked lists.

The output list is not counted as extra working space.

## Implementation

```python
class Solution:
    def addTwoNumbers(
        self,
        l1: 'Optional[ListNode]',
        l2: 'Optional[ListNode]',
    ) -> 'Optional[ListNode]':
        stack1 = []
        stack2 = []

        while l1:
            stack1.append(l1.val)
            l1 = l1.next

        while l2:
            stack2.append(l2.val)
            l2 = l2.next

        carry = 0
        head = None

        while stack1 or stack2 or carry:
            total = carry

            if stack1:
                total += stack1.pop()

            if stack2:
                total += stack2.pop()

            carry = total // 10
            digit = total % 10

            node = ListNode(digit)
            node.next = head
            head = node

        return head
```

## Code Explanation

First, we collect the digits:

```python
stack1 = []
stack2 = []
```

Each linked list is scanned from head to tail.

```python
while l1:
    stack1.append(l1.val)
    l1 = l1.next
```

After this, the top of the stack is the least significant digit.

The addition loop continues while there is still work:

```python
while stack1 or stack2 or carry:
```

We begin each column with the previous carry:

```python
total = carry
```

Then we add one digit from each stack if available:

```python
if stack1:
    total += stack1.pop()

if stack2:
    total += stack2.pop()
```

The carry and output digit are computed by:

```python
carry = total // 10
digit = total % 10
```

The new node is inserted at the front:

```python
node = ListNode(digit)
node.next = head
head = node
```

This keeps the result in most-significant-first order.

## Testing

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

def build_list(values):
    dummy = ListNode()
    curr = dummy

    for value in values:
        curr.next = ListNode(value)
        curr = curr.next

    return dummy.next

def to_list(head):
    values = []

    while head:
        values.append(head.val)
        head = head.next

    return values

def run_tests():
    s = Solution()

    assert to_list(
        s.addTwoNumbers(
            build_list([7, 2, 4, 3]),
            build_list([5, 6, 4]),
        )
    ) == [7, 8, 0, 7]

    assert to_list(
        s.addTwoNumbers(
            build_list([2, 4, 3]),
            build_list([5, 6, 4]),
        )
    ) == [8, 0, 7]

    assert to_list(
        s.addTwoNumbers(
            build_list([0]),
            build_list([0]),
        )
    ) == [0]

    assert to_list(
        s.addTwoNumbers(
            build_list([9, 9, 9]),
            build_list([1]),
        )
    ) == [1, 0, 0, 0]

    assert to_list(
        s.addTwoNumbers(
            build_list([1]),
            build_list([9, 9, 9]),
        )
    ) == [1, 0, 0, 0]

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| `[7,2,4,3] + [5,6,4]` | Checks standard example |
| Equal length lists | Checks ordinary carry handling |
| Both zero | Checks smallest value |
| Final carry | Checks creation of a new leading digit |
| Unequal lengths | Checks missing digits are treated as zero |