Ruairí O'Brien

Posted on

# Day 12 - Add Two Numbers

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

``````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

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]),
],
)
list_root1 = toListNode(l1)
list_root2 = toListNode(l2)
``````

## 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()

class Solution:
def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
carry = 0
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.