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