Add Two Numbers

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 the statement’s third example, l1 = [9,9,9,9,9,9,9] (9999999) and l2 = [9,9,9,9] (9999), watch two things: a missing node counts as 0 once a list runs out, and the loop does not stop when both lists are empty if the carry is still nonzero:

Read from the head of each list

9▲

null▲

9▲

null▲

This step

—v1+—v2+—carry=—total—digit= total % 10—carry out= total // 10

Result list — building

dummy

empty▲

1 / 10

currentcomparingseenresult

Start with carry 0 and an empty result holding only the dummy node. Each list is read from its head, which is the least significant digit.

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.

Convert to Integers

Digit-by-Digit With Carry

More Linked List practice