Add Two Numbers · DSA Prep

Because digits are stored least-significant-first, this is really elementary school addition read left to right: add the two current digits plus any carry, keep the ones digit, carry the tens digit forward. The reversed storage order is what makes that easy — no need to align digits from the right first.

Convert to Integers

Time O(n + m)Space O(n + m)

Walk each list once to reconstruct the actual integer it represents, add the two integers with normal Python arithmetic, then walk the digits of the sum to build a new list. This works because Python integers have unbounded precision, but it does not generalize to languages with fixed-width integers, and it still needs O(n + m) space for the result list regardless.

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution:
    def addTwoNumbers(self, l1: ListNode | None, l2: ListNode | None) -> ListNode | None:
        def to_int(node: ListNode | None) -> int:
            num, place = 0, 1
            while node:
                num += node.val * place
                place *= 10
                node = node.next
            return num

        total = to_int(l1) + to_int(l2)

        if total == 0:
            return ListNode(0)

        dummy = ListNode()
        tail = dummy
        while total:
            tail.next = ListNode(total % 10)
            tail = tail.next
            total //= 10
        return dummy.next

Simple, but it treats the lists as numbers to parse rather than working with the list structure directly — the pointer-based approach below is both more general and no more complex.

Digit-by-Digit With Carry

OptimalTime O(max(n, m))Space O(max(n, m))

Walk both lists simultaneously, adding corresponding digits plus a running carry. Treat a missing node (one list shorter than the other) as digit 0. Keep going as long as there are digits left in either list or a carry still needs to be placed — that last case is what produces the extra leading digit in 999... + 9999.

class Solution:
    def addTwoNumbers(self, l1: ListNode | None, l2: ListNode | None) -> ListNode | None:
        dummy = ListNode()
        tail = dummy
        carry = 0

        while l1 or l2 or carry:
            v1 = l1.val if l1 else 0
            v2 = l2.val if l2 else 0
            total = v1 + v2 + carry
            carry = total // 10
            tail.next = ListNode(total % 10)
            tail = tail.next
            l1 = l1.next if l1 else None
            l2 = l2.next if l2 else None

        return dummy.next

Tracing l1 = [2,4,3] (342), l2 = [5,6,4] (465) — building the result list one digit at a time:

▲tail

1 / 3

2 + 5 + carry(0) = 7. No carry out. Append digit 7.

Why it’s correct: this mirrors manual addition digit by digit from the least-significant end, which is exactly the order these lists are already stored in — the carry correctly propagates overflow into the next position, and continuing the loop while carry is truthy handles the case where the sum has one more digit than either input (e.g. 9999999 + 9999). Complexity: each list is walked once, with the longer list determining the number of iterations, plus at most one extra digit for a final carry → O(max(n, m)) time. The output list has at most max(n, m) + 1 nodes → O(max(n, m)) space — optimal, since the result must contain at least as many digits as the larger input.