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.
Input: l1 = [2,4,3], l2 = [5,6,4] Output: [7,0,8] Explanation: 342 + 465 = 807.
Input: l1 = , l2 =  Output: 
Input: l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9] Output: [8,9,9,9,0,0,0,1]
- The number of nodes in each linked list is in the range
0 <= Node.val <= 9
- It is guaranteed that the list represents a number that does not have leading zeros.
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]), (, , ), ([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
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
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(l2) with potentially 1 more node added at the end for a carried sum.