DSA Adding Two Numbers as Lists

The problem

Add Two Numbers adds two whole numbers that are stored as linked lists of digits. Reverse order means the head node holds the ones column, the next node holds the tens column, and so on. The answer is a new list in the same reverse order holding the sum.

The cases below are the ones this article tests every solution against. One case ends in a carry that adds a whole new column to the answer.

cases = [
    ([2, 4, 3], [5, 6, 4], [7, 0, 8]),
    ([9, 9, 9, 9], [9, 9], [8, 9, 0, 0, 1]),
    ([0], [0], [0]),
    ([5], [5], [0, 1]),
]
for a, b, expected in cases:
    print("digits", a, "+", b, "-> sum digits:", expected)

Read the first row as ordinary addition turned around. The lists hold 342 and 465, and the answer list holds 807, least significant digit first. Writing the numbers backwards in the lists is what lets the addition start at the head.

Intuition: turn the lists back into numbers

The first idea rebuilds each whole number from its digits, adds the two numbers, and splits the sum back into a list. Place value does the rebuilding. The ones digit counts once, the tens digit counts ten times, and so on.

The idea works on short numbers. Its weakness is the numbers themselves. A list can hold thousands of digits, and the rebuilt integer must hold all of them at once, with arithmetic that grows costlier as the integer grows.

class Node:
    def __init__(self, value):
        self.value = value
        self.next = None

def build(digits):
    nodes = [Node(d) for d in digits]
    for i in range(len(nodes) - 1):
        nodes[i].next = nodes[i + 1]
    return (nodes[0] if nodes else None), nodes

def to_list(head):
    out = []
    node = head
    while node is not None:
        out.append(node.value)
        node = node.next
    return out

def to_number(head):
    number = 0
    place = 1
    node = head
    while node is not None:
        number += node.value * place
        place *= 10
        node = node.next
    return number

a, _ = build([2, 4, 3])
b, _ = build([5, 6, 4])
print("first number:", to_number(a))
print("second number:", to_number(b))
print("sum:", to_number(a) + to_number(b))

School addition never builds the whole numbers. It adds one column at a time and carries the overflow. The brute force below keeps the rebuilding route so its digit handling can be counted, and the optimal solution then switches to columns.

Brute force: convert, add, convert back

The brute force converts both lists to integers, adds them, and converts the sum back into a list. A counter records every digit read and written. The conversions touch each digit, and they also build and split one large integer.

class Node:
    def __init__(self, value):
        self.value = value
        self.next = None

def build(digits):
    nodes = [Node(d) for d in digits]
    for i in range(len(nodes) - 1):
        nodes[i].next = nodes[i + 1]
    return (nodes[0] if nodes else None), nodes

def to_list(head):
    out = []
    node = head
    while node is not None:
        out.append(node.value)
        node = node.next
    return out

def add_brute(a, b):
    handled = 0
    def to_number(head):
        nonlocal handled
        number = 0
        place = 1
        node = head
        while node is not None:
            number += node.value * place
            place *= 10
            handled += 1
            node = node.next
        return number
    total = to_number(a) + to_number(b)
    digits = []
    if total == 0:
        digits = [0]
        handled += 1
    while total > 0:
        digits.append(total % 10)
        handled += 1
        total //= 10
    head, _ = build(digits)
    return head, handled

cases = [([2, 4, 3], [5, 6, 4]), ([9, 9, 9, 9], [9, 9]), ([0], [0])]
for da, db in cases:
    a, _ = build(da)
    b, _ = build(db)
    result, handled = add_brute(a, b)
    print("digits", da, "+", db, "->", to_list(result), "digits handled:", handled)

Python integers accept any size, so this route never overflows here. In many languages the rebuilt number overflows a fixed-size integer type quickly. Even in Python, the column method below does strictly less, one small addition per column.

The optimal solution: add column by column with a carry

A carry is the overflow passed to the next column when a column total reaches ten, and walking both lists together while adding one column and its carry at a time builds the sum without ever forming the whole numbers. That one sentence is the whole method.

A dummy head is a throwaway first node placed before the answer. It makes the first real column follow the same rule as every later column, so the building loop needs no special first step. The answer is the dummy's next node.

class Node:
    def __init__(self, value):
        self.value = value
        self.next = None

def build(digits):
    nodes = [Node(d) for d in digits]
    for i in range(len(nodes) - 1):
        nodes[i].next = nodes[i + 1]
    return (nodes[0] if nodes else None), nodes

def to_list(head):
    out = []
    node = head
    while node is not None:
        out.append(node.value)
        node = node.next
    return out

def add(a, b):
    dummy = Node(0)
    tail = dummy
    carry = 0
    while a is not None or b is not None or carry:
        total = carry
        if a is not None:
            total += a.value
            a = a.next
        if b is not None:
            total += b.value
            b = b.next
        carry = total // 10
        tail.next = Node(total % 10)
        tail = tail.next
    return dummy.next

cases = [
    ([2, 4, 3], [5, 6, 4], [7, 0, 8]),
    ([9, 9, 9, 9], [9, 9], [8, 9, 0, 0, 1]),
    ([0], [0], [0]),
    ([5], [5], [0, 1]),
]
for da, db, expected in cases:
    a, _ = build(da)
    b, _ = build(db)
    result = to_list(add(a, b))
    print("digits", da, "+", db, "->", result, "expected:", expected, "match:", result == expected)

All four cases from the start of the article pass. The loop condition carries three parts, and each part matters. The walk continues while either list has digits left or a carry remains, so a final carry becomes a final column.

Walkthrough: 9999 + 99, column by column

The walk adds the second case column by column. Each row prints the two digits, the incoming carry, the total, the digit written, and the carry passed on. Missing digits in the shorter list count as zero.

class Node:
    def __init__(self, value):
        self.value = value
        self.next = None

def build(digits):
    nodes = [Node(d) for d in digits]
    for i in range(len(nodes) - 1):
        nodes[i].next = nodes[i + 1]
    return (nodes[0] if nodes else None), nodes

def to_list(head):
    out = []
    node = head
    while node is not None:
        out.append(node.value)
        node = node.next
    return out

a, _ = build([9, 9, 9, 9])
b, _ = build([9, 9])
carry = 0
column = 0
written = []
while a is not None or b is not None or carry:
    da = a.value if a is not None else 0
    db = b.value if b is not None else 0
    total = da + db + carry
    print("column", column, "- digits", da, "and", db, "carry in:", carry, "total:", total, "writes:", total % 10, "carry out:", total // 10)
    written.append(total % 10)
    carry = total // 10
    column += 1
    if a is not None:
        a = a.next
    if b is not None:
        b = b.next
print("sum digits:", written)

Four columns write 8, 9, 0, 0 while the carry keeps passing. Both lists then run out, but the carry remains, so a fifth column runs and writes the final 1. The sum is 10098, read off the written digits in reverse.

Complexity

The column method visits each column once, so its time is O(max of m and n) for lists of m and n digits. Every column total is at most 19, so each step is one small fixed-size addition.

The answer list holds one node per column of the sum, so the output space is O(max of m and n). Beyond the answer, the method stores one carry and a few pointers, which is O(1) extra space.

for digits in [3, 5, 10]:
    columns = digits
    carry = 1
    print("digits per list:", digits, "columns added:", columns, "final carry adds one column:", carry == 1, "answer digits:", columns + carry)

The conversion route handles the same digits twice and splits the sum as a third pass, all through a growing integer. The column counts above grow one for one with the input and never more. That flat rate is the method's whole claim.

Edge cases and pitfalls

Stopping when both lists end, without checking the carry, is the classic bug. The sum 5 + 5 then loses its final column and reports 0 instead of 10. The walkthrough showed the same failure waiting at the end of 9999 + 99.

Unequal lengths need no padding step. A missing node contributes zero to its column, which is exactly what the conditional reads in the optimal code do.

class Node:
    def __init__(self, value):
        self.value = value
        self.next = None

def build(digits):
    nodes = [Node(d) for d in digits]
    for i in range(len(nodes) - 1):
        nodes[i].next = nodes[i + 1]
    return (nodes[0] if nodes else None), nodes

def to_list(head):
    out = []
    node = head
    while node is not None:
        out.append(node.value)
        node = node.next
    return out

def add(a, b):
    dummy = Node(0)
    tail = dummy
    carry = 0
    while a is not None or b is not None or carry:
        total = carry
        if a is not None:
            total += a.value
            a = a.next
        if b is not None:
            total += b.value
            b = b.next
        carry = total // 10
        tail.next = Node(total % 10)
        tail = tail.next
    return dummy.next

for da, db in [([0], [0]), ([5], [5]), ([9, 9, 9, 9], [9, 9]), ([1, 2], [9]), ([8], [])]:
    a, _ = build(da)
    b, _ = build(db)
    print("digits", da, "+", db, "->", to_list(add(a, b)))

The last row treats an empty list as the number zero, and the walk handles it with no branch of its own. Zero plus zero writes a single zero node. The answer for zero is one digit, never an empty list.