Add two numbers stored as digit lists in Python

Why it matters

Python's int has no fixed size limit. It grows to fit the number, as far as the machine's memory allows. For example, 2**100 prints exactly as 1267650600228229401496703205376. So in Python you rarely need to add big numbers by hand.

This lesson still matters for two reasons. The method is a common exercise in technical interviews, where you are asked to write it without the built-in big integers. And it teaches the same column-by-column work that a computer does when a number is too large for one machine word, which is the case in many other languages.

The method stores each digit as its own node in a linked list. You walk the two lists together, add the digits in each position, and build a new list for the answer. The main new idea is the carry, which is the part of a sum that does not fit in one digit and moves to the next position. A carry is easy to handle with pencil and paper, but a list needs care so that it does not lose a carry at the end.

The linked list basics it relies on are covered in the singly linked lists lesson earlier in this module.

Words you will need

• Digit: one of the symbols 0 to 9.
• Linked list: a chain of nodes. Each node holds one value and a reference to the next node. A reference is a name that points at an object. The last node points to None, which means "there is no next node".
• Carry: the tens part of a column's sum, which moves to the next column. For example, in 8 + 5 = 13, the digit written is 3 and the carry is 1.
• Dummy head: a node that holds no real value and sits in front of the real first node. It is explained in its own section below.
• Integer division (//): divides and drops the fraction. 14 // 10 is 1.
• Remainder (%): what is left over after division. 14 % 10 is 4.

Writing numbers as chains

Here is a number stored as a chain. The number is 342, and it is stored with the ones digit first:

2 -> 4 -> 3 -> None

The first node holds 2, which is the ones digit. The second node holds 4, which is the tens digit. The third node holds 3, which is the hundreds digit. Reading the chain from left to right gives the digits from the smallest place value to the largest.

This order is the key to the whole lesson. When you add two numbers on paper, you start at the ones column on the right and move left. If the digits are stored with the ones digit first, the first node of each list is the first column you need. You can walk both lists from their heads, one step at a time, and the walk matches the way you add by hand.

The opposite order, with the most significant digit first, is also possible. Then you would need to reverse both lists or use a stack, which is a different kind of work. The examples here use the ones-digit-first order, because it lets one pass do all the work.

The node class

The code in this lesson uses one small class for a node. It has a value and a next reference.

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

__init__ runs when a node is created. It sets the value and sets next to None, which means the new node points at nothing yet.

We also need a way to build a list from a sequence of digits and a way to turn a list back into a Python list so we can print it.

def from_digits(*digits):
    dummy = ListNode(0)
    tail = dummy
    for d in digits:
        tail.next = ListNode(d)
        tail = tail.next
    return dummy.next
 
 
def to_list(head):
    out = []
    cur = head
    while cur is not None:
        out.append(cur.val)
        cur = cur.next
    return out

The *digits in from_digits collects any number of arguments into a tuple. Calling from_digits(2, 4, 3) gives digits the value (2, 4, 3). The same star works in the other direction. from_digits(*[2, 4, 3]) unpacks the list into three separate arguments, and the result is the same.

The variable named dummy is a dummy head. It is a node that holds no real value and sits in front of the real first node. We come back to why it helps in a later section.

The idea: one column at a time

Before the code, here is the addition done by hand. We add 342 and 465. The digits are shown in the order we store them, so the ones column comes first.

Column one, the ones: 2 plus 5 is 7. Write 7. The carry is 0.

Column two, the tens: 4 plus 6 is 10. Ten does not fit in one digit. Write the ones digit of 10, which is 0. The carry is 1, because one ten moves to the next column.

Column three, the hundreds: 3 plus 4 plus the carry 1 is 8. Write 8. The carry is 0.

The answer is 807, stored as the list 7 -> 0 -> 8.

Each column needs three steps. Add the two digits and the carry from the previous column. Write the ones digit of the sum. Keep the tens digit as the carry for the next column. In Python, the ones digit is total % 10 and the carry is total // 10. The % operator gives the remainder after division, and the // operator divides and drops the fraction. So 14 % 10 is 4, and 14 // 10 is 1.

Python also has /, which gives a decimal result. 14 / 10 is 1.4, not 1. Using / by mistake is covered in the Common mistakes section.

Example 1: 342 plus 465

Here is the full method. It is the core of the lesson, so read it slowly.

def add_two_numbers(a, b):
    dummy = ListNode(0)
    tail = dummy
    carry = 0
    while a is not None or b is not None or carry != 0:
        total = carry
        if a is not None:
            total += a.val
            a = a.next
        if b is not None:
            total += b.val
            b = b.next
        tail.next = ListNode(total % 10)
        tail = tail.next
        carry = total // 10
    return dummy.next

The loop runs once for each column. It keeps going while at least one of three things is true. Either list a still has a node, or list b still has a node, or there is still a carry to write. The third condition is the one that beginners forget, and we look at it in the next example.

Inside the loop, total starts at the carry from the last column. If a has a node, we add its value and move a to the next node. The same is done for b. Now total holds the total for this column. The line tail.next = ListNode(total % 10) creates the answer node for this column and attaches it to the end of the answer list. Then tail moves onto that new node, so the next column attaches after it. The last line sets the carry for the next column.

Python also accepts while a or b or carry:, because a node is always true when it is used as a condition. The lesson uses is not None so the check says what it means.

Here is the code with a print statement added. It runs the example above and four more. This is a complete program, and it prints the outputs shown below.

The output, from running the program above on Python 3.14, is:

342 + 465 -> [7, 0, 8]
99 + 1 -> [0, 0, 1]
0 + 0 -> [0]
9999999 + 9999 -> [8, 9, 9, 9, 0, 0, 0, 1]
5 + 5 -> [0, 1]

The first line matches the hand calculation: 7, 0, 8, which reads as 807.

Example 2: the carry that creates a new digit

Look at the second line of output: 99 + 1 gives [0, 0, 1]. The answer is 100, which has three digits, but the inputs have only two digits each.

Walk through it. The first column is 9 plus 1, which is 10. The digit written is 0, and the carry is 1. The second column is 9 plus nothing plus the carry 1, which is 10. The digit written is 0, and the carry is 1 again. Now both lists have ended, so a and b are None. The loop condition is still true because carry is 1. The third column is 0 plus 0 plus the carry 1, which is 1. The digit written is 1, and the carry is 0. Now every condition is false, and the loop ends.

Without the third condition, the loop would stop after the second column, and the answer would be [0, 0]. That is the wrong answer, because the carry of 1 would be dropped. This is the first mistake covered in the Common mistakes section below.

The same idea explains 5 + 5, which is 10. Both inputs have one digit. The first column is 5 plus 5, which is 10. The digit written is 0, and the carry is 1. The loop runs once more because of the carry, and writes the digit 1. The answer is [0, 1], which is 10 with the ones digit first.

Example 3: unequal lengths and a long answer

The third example is harder because the two lists have different lengths, and the answer is one digit longer than the longer input.

Take 9999999 plus 9999. The first list has seven nodes, and the second has four. Here is the work for the first few columns. Each row shows the digits read from the two lists, the carry coming in, the sum, the digit written, and the carry going out.

column  a  b  carry_in  sum  written  carry_out
1       9  9  0          18   8        1
2       9  9  1          19   9        1
3       9  9  1          19   9        1
4       9  9  1          19   9        1
5       9  -  1          10   0        1
6       9  -  1          10   0        1
7       9  -  1          10   0        1
(end)   -  -  1           1   1        0

The row with - shows a list that has already ended. The method treats a missing node as the digit 0, because the code only adds a.val when a is not None. On those rows only list a adds a digit, so column 5 is 9 plus the carry 1, which is 10.

The written digits are 8, 9, 9, 9, 0, 0, 0, 1. Read them from right to left, and you get the answer 10009998. The output line [8, 9, 9, 9, 0, 0, 0, 1] is the same answer.

Notice what happens at column 5. The first list still has a 9, but the second list has ended. The code does not need a special case. The check if b is not None: skips the second list, and the loop goes on using the carry and the first list only. This is why the three-part loop condition handles both unequal lengths and the final carry in one place.

The dummy head

The method creates a node called dummy before the loop. The answer list starts at dummy.next, and the method returns dummy.next at the end.

Why not start with the first answer node directly? The first node of the answer is the only node that has no node before it, so we would need an extra case to set the head of the answer. Without the dummy, the code would look like this:

if the answer is empty, set head to the new node
otherwise, attach the new node to tail

That check runs inside every loop pass. The dummy removes it. Every node, including the first, is attached to some node that already exists, which is tail in the first pass and the previous answer node in later passes. The dummy is thrown away at the end, and the caller gets the real first node.

You can write the function without a dummy, and it still works. Here is the version with the check.

def add_without_dummy(a, b):
    head = None
    tail = None
    carry = 0
    while a is not None or b is not None or carry != 0:
        total = carry
        if a is not None:
            total += a.val
            a = a.next
        if b is not None:
            total += b.val
            b = b.next
        node = ListNode(total % 10)
        if head is None:
            head = node
        else:
            tail.next = node
        tail = node
        carry = total // 10
    return head

Its output matches the dummy version:

[7, 0, 8]
[0, 1]

Both versions are correct. The dummy version has fewer branches, so there are fewer places to make a mistake. Use whichever you can explain clearly.

Common mistakes

Dropping the final carry

The most common mistake is to write the loop condition as while a is not None or b is not None:. This looks natural, because the loop seems to be about the lists. But the carry can still be 1 after both lists end. Here is the bug, run on 99 + 1. The function no_final_carry uses the shorter condition.

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

[0, 0]

The answer should be [0, 0, 1]. The one-digit answer for the last column was never written. The fix is to add or carry != 0 to the loop condition.

Reading a missing node

A second mistake is to add the two values without checking for None first. This is easy to do when the two lists have the same length in your test, because you never see the problem. Here is a function that always reads a.val and b.val:

total = a.val + b.val + carry

When b has run out, b is None. Reading b.val on None is an error. Python stops the program and prints an error message. This is the real output from running that function on 342 plus 65, which has a shorter second list. The File lines of the traceback, which name the file and line number, are left out here, because they depend on where you saved the file.

    total = a.val + b.val + carry
                    ^^^^^
AttributeError: 'NoneType' object has no attribute 'val'

The message names the problem. AttributeError means you asked an object for a field it does not have. The text 'NoneType' says the object was None, and the caret ^^^^^ points at b.val, the part that failed. The fix is the check if b is not None: used in the lesson's method.

Using / instead of //

In Python 3, the operator / always gives a decimal result, even when both numbers are whole. So total / 10 gives 1.0, not 1. The carry becomes a decimal, and the loop never sees a carry of 0 in the usual way. The loop keeps going, writing tiny decimal digits, until the carry shrinks to zero after many steps.

carry = total / 10

Running a version with / on 5 + 5 gives a list of 325 numbers. Only the first four are shown here:

[0, 1.0, 0.1, 0.01, ...

The fix is //, which divides and drops the fraction. Use // for the carry and % for the digit.

Mixing up the digit order

If one list is stored with the ones digit first and the other with the most significant digit first, the sum is wrong, and no error is shown. The method adds the first node of each list together, so it adds the ones digit of one number to the millions digit of the other. Always check which order the input uses before you write the loop.

Practice

Exercise 1

Add the list 5 and the list 5 by hand, using the three steps for each column. Then check the answer with the code.

Show the answer

By hand, the single column is 5 plus 5, which is 10. Write 0, and the carry is 1. The loop runs again because of the carry, and writes 1. The answer is [0, 1], which is 10. The program prints 5 + 5 -> [0, 1].

Exercise 2

Add the number 100, stored as 0 -> 0 -> 1, and the number 10000, stored as 0 -> 0 -> 0 -> 0 -> 1. Write the answer as a list, and say what number it is.

Show the answer

The answer list is [0, 0, 1, 0, 1]. Reading it from the most significant digit gives 1, 0, 1, 0, 0, which is 10100. The first two columns are 0 plus 0, so they write 0 and 0. The third column is 1 plus 0, which writes 1. The fourth column has only a digit from the second list, which is 0, and writes 0. The fifth column is 1, which writes 1. Calling to_list(add_two_numbers(from_digits(0, 0, 1), from_digits(0, 0, 0, 0, 1))) returns [0, 0, 1, 0, 1].

Exercise 3

Add 1 to 999. Use the function add_two_numbers and pass a list for 1 as the second argument.

Show the answer

Call add_two_numbers(from_digits(9, 9, 9), from_digits(1)). The first column is 9 plus 1, which is 10, so it writes 0 and carries 1. The second and third columns are 9 plus the carry, which is 10 each time, so they write 0 and carry 1. The fourth column has no digits left and only the carry 1, so it writes 1. The answer is [0, 0, 0, 1], which is 1000.

Exercise 4

Explain why the loop condition checks carry != 0 as well as the two list checks. Give one example where removing that part gives a wrong answer.

Show the answer

The carry is the value that moves to the next column. After both lists have ended, the carry can still be 1, and that 1 has to be written as one more digit. Removing the check drops that digit. For 99 + 1, the loop stops after the second column, and the answer becomes [0, 0] instead of [0, 0, 1].

Exercise 5

What does add_two_numbers(None, None) return, and why?

Show the answer

It returns None. Both lists are empty, so the loop condition is false on the first check: both lists are None and the carry is 0. The loop never runs, dummy.next is still None, and the function returns it.

Summary

• A number can be stored as a linked list of digits with the ones digit first, so that the first node is the first column to add.
• Each column adds the two digits and the carry, writes total % 10, and keeps total // 10 as the next carry.
• The loop runs while either list has a node or the carry is not zero. The carry check writes the extra digit in a sum like 99 + 1.
• A missing node counts as a digit 0, which is handled by checking for None before reading val.
• A dummy head removes the special case for the first answer node, and the answer is returned as dummy.next.