## The Problem

You are given two

non-emptylinked lists representing two non-negative integers. The digits are stored inreverse 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.

## My Tests

```
import pytest
from typing import List
from .util import ListNode, toListNode, toList
from .Day12_AddTwoNumbers import Solution
s = Solution()
@pytest.mark.parametrize(
"l1,l2,expected",
[
([2, 4, 3], [5, 6, 4], [7, 0, 8]),
([0], [0], [0]),
([9, 9, 9, 9, 9, 9, 9], [9, 9, 9, 9], [8, 9, 9, 9, 0, 0, 0, 1]),
],
)
def test_add_two_numbers(l1, l2, expected):
list_root1 = toListNode(l1)
list_root2 = toListNode(l2)
assert toList(s.addTwoNumbers(list_root1, list_root2)) == expected
```

## My Solution

```
from .util import ListNode
def add(carry: int, l1: ListNode, l2: ListNode):
x = l1.val
y = l2.val if l2 is not None else 0
ans = x + y + carry
if ans >= 10:
carry = 1
ans = ans - 10
else:
carry = 0
l1.val = ans
l2_next = l2.next if l2 is not None else None
if l2_next or carry > 0:
if l1.next is None:
l1.next = ListNode()
add(carry, l1.next, l2_next)
class Solution:
def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
carry = 0
add(carry, l1, l2)
return l1
```

## Analysis

## My Commentary

Just did this one the same way I'd do it in my head. Go through each number. Add them. If the sum is great than or equal to 10, carry the one.

Made a small space optimisation by storing the answer in `l1`

. This is `O(n)`

in space and runtime, noting that `n`

is the larger of `len(l1)`

or `len(l2)`

with potentially 1 more node added at the end for a carried sum.

## Top comments (0)