Add Two Numbers

Add Two Numbers takes two numbers stored as linked lists — one digit per node, in reverse order — and adds them. It is the classic exercise in walking two lists at once while carrying overflow, exactly like the long addition you learned in grade school.

The slow way first

The tempting idea: walk each list, rebuild the actual integer it represents, add the two integers, then break the sum back into a list of digits. That works for small inputs, but it falls apart the moment the numbers are longer than a machine word — the lists can hold hundreds of digits, far more than an int can hold. We need to add digit by digit and never form the whole number.

The question to ask: how did I add big numbers by hand? Right-to-left, one column at a time, carrying a 1 when a column overflows past 9. The reversed list order hands us the digits in exactly that right-to-left sequence.

The idea: long addition with a carry

Walk both lists together from the head. At each position add the two digits plus the carry from the previous column. The new result digit is sum % 10, and the carry into the next column is sum // 10. When one list runs out, treat its missing digit as 0. Stop only when both lists are exhausted and the carry is 0.

The key detail: do not stop just because both lists ended. A final carry (like adding 5 + 5 in the last column) needs one more node. The loop condition checks the carry too.

Walk through it

Step through the animation. We add the ones place (2 + 5 = 7, no carry), then the tens place (4 + 6 = 10, which writes a 0 and carries a 1), then the hundreds place where that carry matters: 3 + 4 + 1 = 8. The result list grows one node per column: 7→0→8, which reads as 807 in reverse — the correct sum.

Pseudocode

make a dummy head; let cur point at it
carry = 0
while l1 has nodes, or l2 has nodes, or carry is not 0:
    d1 = l1 value if l1 exists else 0
    d2 = l2 value if l2 exists else 0
    sum = d1 + d2 + carry
    carry = sum // 10
    digit = sum % 10
    attach a new node holding digit after cur; advance cur
    advance l1 and l2 if they exist
return the node after the dummy head

The Python solution

def add_two_numbers(l1, l2):
    dummy = ListNode()
    cur = dummy
    carry = 0
    while l1 or l2 or carry:
        s = (l1.val if l1 else 0) + (l2.val if l2 else 0) + carry
        carry, digit = divmod(s, 10)
        cur.next = ListNode(digit)
        cur = cur.next
        l1, l2 = l1.next if l1 else None, l2.next if l2 else None
    return dummy.next

• dummy is a throwaway head node so we never special-case the first append; cur always points at the last result node.
• Line 5 is the loop condition — it keeps going while either list has digits left or there is still a carry to flush.
• Line 6 reads each list value, substituting 0 when a list has run out, and adds the carry.
• divmod(s, 10) on line 7 gives both the new carry (s // 10) and the digit (s % 10) in one call.
• Line 8 builds and links the new result node; the next line advances cur, and the final line advances the two input pointers.

Complexity

We touch each node once, so the time is linear in the length of the longer list. The extra space is the result list itself, which has about the same length.

When this pattern shows up

Practice