• Leetcode 2
• Difficulty: Medium

---

Problem Definition

Given 2 non-empty linked lists representing two non-negative integers, with the digits in reverse order (the $10^0$ elements being first, then the $10^1$ and then $10^2$, ...), add the two numbers and return the sum as a linked list.

---

Digit Class

Below is the class for each node in the linked list, which represents a number. Each such node in the linked list represents a digit in the number.

class Digit:
    def __init__(self, val: int, nxt: 'Digit' = None):
        self.val = val
        self.nxt = nxt

    def __repr__(self):
        return str(self)

    def __str__(self):
        curr = self
        mag = 0
        res = 0
        while curr is not None:
            res += curr.val * (10**mag)
            mag += 1
            curr = curr.nxt
        return str(res)

---

Examples

We start by writing some tests that we will use to verify our solution.

# 1->2->3
# 2->3->4
n1 = Digit(1, nxt=Digit(2, nxt=Digit(3)))
n2 = Digit(2, nxt=Digit(3, nxt=Digit(4)))
n3 = add(n1, n2)
assert str(n3) == "753"

n4 = add(n1, None)
assert str(n4) == "321"

# 2->3
n5 = Digit(2, nxt=Digit(3))
n6 = add(n1, n5)
n7 = add(n5, n1)
assert str(n6) == "353"
assert str(n7) == "353"

# 9->9->9
# 1
n8 = Digit(9, nxt=Digit(9, nxt=Digit(9)))
n9 = Digit(1)
n10 = add(n8, n9)
assert str(n10) == "1000"

---

Solution

def add(n1: Digit, n2: Digit) -> Digit:
    if n1 is None and n2 is None:
        return None
    carry = 0
    if n1 is not None:
        carry += n1.val
        n1 = n1.nxt
    if n2 is not None:
        carry += n2.val
        n2 = n2.nxt
    prev = head = Digit(carry % 10)
    carry = carry // 10
    while n1 is not None or n2 is not None:
        if n1 is not None:
            carry += n1.val
            n1 = n1.nxt
        if n2 is not None:
            carry += n2.val
            n2 = n2.nxt
        prev.nxt = Digit(carry % 10)
        prev = prev.nxt
        carry = carry // 10
    if carry > 0:
        prev.nxt = Digit(carry)
    return head

---

Complexity

Let $n =$ len(n1), $m = $ len(n2).

Since we are looking at each element once, the runtime complexity should be $O(n + m)$.

Auxiliary space complexity should be $O(1)$ since we are storing just a handful of temporary variables.

The space complexity of the returned value, which by definition is not auxiliary, should be $O(max(n, m))$.