Medium

Add Two Numbers

LAB

Two non-empty linked lists store non-negative integers in reverse digit order. Return the sum as a linked list encoded in the same reverse digit order.

EXAMPLES

Example 1

Input
{
  "l1": [
    2,
    4,
    3
  ],
  "l2": [
    5,
    6,
    4
  ]
}

Output
[
  7,
  0,
  8
]

FUNCTION SHAPE

l1: intArrayl2: intArray→intArray

SOLUTION NOTE

Note that dummy = curr = ListNode(0) is equivalent to two lines:

pythonEXAMPLE

curr = ListNode(0)
dummy = curr

NOT

pythonEXAMPLE

curr = ListNode(0)
dummy = ListNode(0)

This is basically just simulating addition of two integers as learned in primary school. We can use divmod to get the quotient and remainder.

Reveal reference solution +

pythonREFERENCE

def addTwoNumbers(self, l1, l2):
    dummy = curr = ListNode(0)
    carry = 0
    while l1 or l2 or carry:
        carry, val = divmod(
            (l1.val if l1 else 0) + (l2.val if l2 else 0) + carry, 10)
        curr.next = ListNode(val)
        curr = curr.next
        if l1: l1 = l1.next
        if l2: l2 = l2.next
    return dummy.next

# Recursive solution
def addTwoNumbersRecursive(self, l1: ListNode, l2: ListNode, carry=0) -> ListNode:
    # Base case: if both lists are empty and no carry
    if not l1 and not l2 and not carry:
        return None

    # Get values (or 0 if the list has ended)
    x = l1.val if l1 else 0
    y = l2.val if l2 else 0

    # Calculate sum and new carry
    total = x + y + carry
    carry = total // 10
    digit = total % 10

    # Create a new node with the digit value
    result = ListNode(digit)

    # Recursively process the next digits
    result.next = self.addTwoNumbersRecursive(
        l1.next if l1 else None,
        l2.next if l2 else None,
        carry
    )

    return result

TimeO(max(n, m))

SpaceO(max(n, m))

Open on LeetCode ↗