Add Two Numbers: Linked List Digit Addition

Add Two Numbers is LeetCode 2. It is one of the first medium problems most people attempt, and it teaches a skill that shows up constantly in linked list problems: building a new linked list node by node while processing inputs.

The trick is not the math. You already know how to add numbers. The trick is doing it inside linked lists while managing a carry, and assembling the result list without losing track of the head.

The problem

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each node contains a single digit. Add the two numbers and return the sum as a linked list, also in reverse order.

Example: 2 -> 4 -> 3 represents 342. 5 -> 6 -> 4 represents 465. The sum is 807, so the output is 7 -> 0 -> 8.

The reverse storage order is actually a gift. It means the ones digit comes first, which is exactly the order you need for addition. No reversal required.

Why this is a linked list problem, not a math problem

Your first instinct might be to convert both lists to integers, add them, and convert back. That works for small inputs, but the problem says the numbers can have up to 100 digits. That overflows every integer type in most languages.

The real approach is to do what you learned in elementary school: add digit by digit, right to left, carrying the overflow. Since the digits are already stored in reverse (ones digit first), you just walk both lists from head to tail and add as you go.

The algorithm

1. Start a carry variable at 0
2. Walk both lists simultaneously
3. At each position, compute sum = digit1 + digit2 + carry
4. The new digit is sum % 10
5. The new carry is sum // 10
6. Create a new node with that digit and attach it to the result list
7. When both lists are exhausted and carry is 0, you are done
8. If carry is still 1 after both lists end, add one more node

The subtle part: the lists can be different lengths. When one list runs out, treat its missing digits as 0. And do not forget the final carry. If the last addition produces a carry (like 999 + 1 = 1000), you need that extra node.

Visual walkthrough

Let's trace through adding 2 -> 4 -> 3 (342) and 5 -> 6 -> 4 (465). Watch how the carry propagates and the result list grows one node at a time.

Notice how each step is identical: grab the current digits (or 0 if a list is exhausted), add them with the carry, write sum % 10, update carry to sum // 10. The loop body does not change regardless of list lengths or carry values.

The solution

def addTwoNumbers(l1, l2):
    dummy = ListNode(0)
    curr = dummy
    carry = 0

    while l1 or l2 or carry:
        val1 = l1.val if l1 else 0
        val2 = l2.val if l2 else 0

        total = val1 + val2 + carry
        carry = total // 10
        curr.next = ListNode(total % 10)
        curr = curr.next

        if l1:
            l1 = l1.next
        if l2:
            l2 = l2.next

    return dummy.next

Let's break this down line by line:

1. Dummy head. dummy = ListNode(0) creates a placeholder node. The real result starts at dummy.next. This avoids special-casing the first node.
2. Loop condition. while l1 or l2 or carry keeps going as long as there are digits left to process or a carry to flush. The or carry part handles the case where both lists are done but you still need to emit a final 1.
3. Safe digit access. l1.val if l1 else 0 treats an exhausted list as producing 0s. This handles different-length lists without branching.
4. Carry arithmetic. total // 10 gives the carry (0 or 1). total % 10 gives the digit to store. These two operations are the entire mathematical core of the algorithm.
5. Build the result. Create a new node and link it in. Advance curr to the new node.
6. Advance inputs. Move each pointer forward only if it is not already null.

Complexity analysis

Time: O(max(m, n)) where m and n are the lengths of the two lists. You visit each node in both lists exactly once. The final carry step adds at most one more iteration.

Space: O(max(m, n)) for the result list. The result list has at most max(m, n) + 1 nodes (the +1 is for a potential final carry). No extra data structures beyond the output.

Edge cases

• Different length lists. 9 -> 9 (99) plus 1 (1) gives 0 -> 0 -> 1 (100). The shorter list runs out first, and you treat its missing digits as 0.
• Carry at the very end. 5 plus 5 gives 0 -> 1. The carry from 5 + 5 = 10 needs an extra node. The or carry in the loop condition handles this.
• One list is a single zero. 0 plus 1 -> 2 -> 3 gives 1 -> 2 -> 3. Works naturally since 0 does not affect the sum.
• Both lists are the same length. The most common case. Nothing special, the algorithm handles it like any other case.

The Building Blocks

This problem is built from two core building blocks:

Carry-digit arithmetic. Given two single digits and a carry-in, compute the output digit and carry-out. total = a + b + carry, digit = total % 10, carry = total // 10. This is elementary school column addition, and it appears in every problem that involves multi-precision arithmetic on linked lists or strings.

Node-by-node rebuild. Build a new linked list one node at a time using a dummy head and a tail pointer. dummy = ListNode(0), curr = dummy, then in a loop: curr.next = ListNode(value), curr = curr.next. Return dummy.next. This pattern appears in any problem where you need to construct a linked list from scratch, like merging two sorted lists, partitioning a list, or deep-copying a list with random pointers.

These two bricks combine to solve the problem cleanly. The arithmetic brick handles the math. The rebuild brick handles the output construction. Separate concerns, each one simple on its own.

Common mistakes

1. Forgetting the final carry. If you loop only while l1 or l2, you miss the case where both lists are exhausted but carry is 1. Always include or carry in the condition.
2. Advancing a null pointer. If l1 is already None, calling l1 = l1.next crashes. Always check before advancing.
3. Returning dummy instead of dummy.next. The dummy node holds a placeholder value (0). The actual result starts at dummy.next.

Why you will forget this (and how to fix it)

This is a 12-line solution. It looks simple. But under pressure, people mess up the loop condition, forget the carry, or stumble on the dummy head setup. The problem is not understanding the algorithm. It is being able to type it from scratch without hesitation.

The carry arithmetic and the node-by-node rebuild are both patterns you need to have in muscle memory. When you see a problem that requires building a new linked list, the dummy head setup should flow from your fingers without thinking. When you see digit-by-digit addition, the % 10 and // 10 pair should be automatic.

Spaced repetition locks this in. Type the solution from scratch today, again in three days, again next week. After a few reps, the loop structure and carry logic become second nature.

Related posts

• Reverse Linked List - The most fundamental linked list pointer manipulation technique, and a building block for many problems that combine with Add Two Numbers
• Linked Lists (Data Structure) - If the node/pointer concepts here feel unfamiliar, start with this guide to linked list fundamentals