# LeetCode 2: Add Two Numbers

## Problem Restatement

We are given two non-empty linked lists.

Each linked list represents a non-negative integer.

The digits are stored in reverse order.

For example:

```text
2 -> 4 -> 3
```

actually represents the number:

```text
342
```

because the least significant digit comes first.

We need to add the two numbers together and return the result as a linked list in the same reversed format.

Each node contains exactly one digit.

## Input and Output

| Item | Meaning |
|---|---|
| Input | Two linked lists `l1` and `l2` |
| Output | A new linked list representing the sum |
| Digit Order | Reverse order |
| Constraint | Each node stores one digit from `0` to `9` |

The linked list node structure:

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

## Examples

Input:

```text
l1 = 2 -> 4 -> 3
l2 = 5 -> 6 -> 4
```

The first list represents:

```text
342
```

The second list represents:

```text
465
```

Their sum is:

```text
342 + 465 = 807
```

Because the output must also be reversed, we return:

```text
7 -> 0 -> 8
```

Another example:

```text
l1 = 0
l2 = 0
```

Result:

```text
0
```

Another example:

```text
l1 = 9 -> 9 -> 9 -> 9
l2 = 1
```

This represents:

```text
9999 + 1 = 10000
```

Result:

```text
0 -> 0 -> 0 -> 0 -> 1
```

The final carry creates a new node.

## First Thought: Convert Everything Into Integers

One possible idea:

1. Traverse the linked list.
2. Convert the digits into integers.
3. Add the integers.
4. Convert the result back into a linked list.

For small numbers, this works.

Example:

```text
2 -> 4 -> 3
```

becomes:

```text
342
```

Then:

```text
342 + 465 = 807
```

Finally:

```text
7 -> 0 -> 8
```

## Problem With Integer Conversion

This approach has several issues.

The linked lists may become very large.

Some languages cannot safely store extremely large integers.

More importantly, the problem is designed to test linked list manipulation and digit-by-digit arithmetic.

We should solve the problem directly using the linked lists themselves.

## Key Insight

This problem behaves exactly like elementary school addition.

When adding two numbers by hand:

1. Add the current digits.
2. Add the carry from the previous step.
3. Write down the current digit.
4. Carry the overflow into the next column.

Example:

```text
  342
+ 465
-----
  807
```

Digit by digit:

```text
2 + 5 = 7
4 + 6 = 10
3 + 4 + 1 = 8
```

The linked lists already store digits from least significant to most significant.

That means we can process them naturally from left to right.

## Visual Walkthrough

Start:

```text
l1: 2 -> 4 -> 3
l2: 5 -> 6 -> 4
carry = 0
```

First digits:

```text
2 + 5 + 0 = 7
```

Write digit:

```text
7
```

New carry:

```text
0
```

Second digits:

```text
4 + 6 + 0 = 10
```

Write digit:

```text
0
```

Carry:

```text
1
```

Third digits:

```text
3 + 4 + 1 = 8
```

Write digit:

```text
8
```

Carry:

```text
0
```

Final result:

```text
7 -> 0 -> 8
```

## Algorithm

We maintain:

| Variable | Meaning |
|---|---|
| `carry` | Overflow from previous digit |
| `dummy` | Fake head node for easier construction |
| `current` | Tail of the result list |

Loop while:

- `l1` still exists
- or `l2` still exists
- or `carry` is non-zero

For every step:

1. Read the current digit from `l1`
2. Read the current digit from `l2`
3. Add both digits and the carry
4. Compute:
   - new digit
   - new carry
5. Create a new node
6. Move forward

The important formulas are:

Current digit:

$$
\text{digit} = (x + y + \text{carry}) \bmod 10
$$

New carry:

$$
\text{carry} = \left\lfloor \frac{x + y + \text{carry}}{10} \right\rfloor
$$

## Correctness

At every iteration, we process exactly one decimal position.

Suppose:

- `x` is the current digit from `l1`
- `y` is the current digit from `l2`
- `carry` is the overflow from the previous position

Then:

```text
x + y + carry
```

represents the correct sum for the current decimal place.

The ones digit becomes the node value.

The tens digit becomes the carry for the next iteration.

This matches exactly how decimal addition works.

The loop continues until:

- both linked lists are exhausted
- and no carry remains

Therefore every digit of the final sum is constructed correctly.

## Complexity

| Metric | Value | Why |
|---|---|---|
| Time | `O(max(n, m))` | We traverse each list once |
| Space | `O(max(n, m))` | The result list stores the sum |

Where:

- `n` is the length of `l1`
- `m` is the length of `l2`

## Implementation

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

class Solution:
    def addTwoNumbers(
        self,
        l1: ListNode,
        l2: ListNode
    ) -> ListNode:

        dummy = ListNode()
        current = dummy

        carry = 0

        while l1 or l2 or carry:
            x = l1.val if l1 else 0
            y = l2.val if l2 else 0

            total = x + y + carry

            digit = total % 10
            carry = total // 10

            current.next = ListNode(digit)

            current = current.next

            if l1:
                l1 = l1.next

            if l2:
                l2 = l2.next

        return dummy.next
```

## Code Explanation

We first create a dummy node:

```python
dummy = ListNode()
```

This simplifies linked list construction.

Without a dummy node, we would need special handling for the first element.

`current` always points to the tail of the result list.

```python
current = dummy
```

We maintain the carry:

```python
carry = 0
```

Inside the loop:

```python
x = l1.val if l1 else 0
y = l2.val if l2 else 0
```

If one list becomes shorter, we treat missing digits as `0`.

Then:

```python
total = x + y + carry
```

Extract the new digit:

```python
digit = total % 10
```

Extract the carry:

```python
carry = total // 10
```

Create the next node:

```python
current.next = ListNode(digit)
```

Move forward:

```python
current = current.next
```

Finally:

```python
return dummy.next
```

We skip the dummy node and return the real head.

## Testing

Helper functions:

```python
def build_list(values):
    dummy = ListNode()
    current = dummy

    for v in values:
        current.next = ListNode(v)
        current = current.next

    return dummy.next

def to_list(node):
    result = []

    while node:
        result.append(node.val)
        node = node.next

    return result
```

Tests:

```python
def run_tests():
    s = Solution()

    l1 = build_list([2, 4, 3])
    l2 = build_list([5, 6, 4])

    assert to_list(s.addTwoNumbers(l1, l2)) == [7, 0, 8]

    l1 = build_list([0])
    l2 = build_list([0])

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

    l1 = build_list([9, 9, 9, 9])
    l2 = build_list([1])

    assert to_list(s.addTwoNumbers(l1, l2)) == [0, 0, 0, 0, 1]

    l1 = build_list([1, 8])
    l2 = build_list([0])

    assert to_list(s.addTwoNumbers(l1, l2)) == [1, 8]

    print("all tests passed")

run_tests()
```

| Test | Why |
|---|---|
| Standard example | Basic correctness |
| Zero values | Smallest valid input |
| Final carry overflow | Checks extra node creation |
| Different list lengths | Confirms missing digits handled correctly |