Add Two Numbers as a Linked List

Before we start

This problem sounds like arithmetic homework, but it teaches one of the most reusable linked list tricks: the dummy head node that makes result-list construction uniform from the very first digit. It also reinforces carry propagation — a concept that appears in binary addition, multiply strings, and big-number arithmetic problems. By the end you will be able to:

• Build a result linked list digit by digit using a dummy head.
• Handle carries correctly including the carry-out after the last digit.
• Adapt the solution for digits stored in forward order (LC #445) using a stack.

Picture this first (no code yet)

The actual problem

Add Two Numbers (LC #2):

Two non-empty linked lists represent two non-negative integers where digits are stored in reverse order (head = least-significant digit). Add them and return the sum as a linked list in the same format.

l1 = 2 → 4 → 3 represents 342.
l2 = 5 → 6 → 4 represents 465.
Sum = 807, returned as 7 → 0 → 8.

Constraints: no leading zeros (except the number 0 itself); digits 0–9; up to 100 nodes each.

First, the slow way (so you feel the pain)

Convert both lists to Python integers (traverse, build digit string, int()), add them, convert the sum back to a new linked list. This works for small numbers, but Python integers can hold arbitrarily large values while linked list problems in Java or C++ overflow 64-bit integers. The intended solution works digit by digit regardless of number length — no integer conversion required.

The turning point

The one idea to remember

The code

def addTwoNumbers(l1, l2):
    dummy = ListNode(0)   # sentinel: avoids special-casing head
    cur   = dummy
    carry = 0

    while l1 or l2 or carry:
        val1  = l1.val if l1 else 0     # treat exhausted list as 0
        val2  = l2.val if l2 else 0
        total = val1 + val2 + carry

        carry     = total // 10          # carry to next column
        cur.next  = ListNode(total % 10) # write this column's digit
        cur       = cur.next             # advance result pointer

        if l1: l1 = l1.next             # advance input pointers
        if l2: l2 = l2.next

    return dummy.next    # skip the sentinel, return real head

Line-by-line narration:

1. dummy = ListNode(0) — a throwaway node. Its only purpose: give cur a valid next to write to from the very first iteration, so we never need "if this is the first node, set head; else append."
2. cur = dummy — cur tracks the tail of the result list.
3. carry = 0 — starts at zero; accumulates whenever a column sums ≥ 10.
4. while l1 or l2 or carry: — keep going as long as there are digits left or a carry remains. The or carry is the crucial clause that handles the extra leading digit.
5. val1 = l1.val if l1 else 0 — safe: if l1 is exhausted, treat it as 0.
6. total = val1 + val2 + carry — column sum including carry-in.
7. carry = total // 10 — carry-out: 0 if total < 10, else 1 (sum of two single digits + carry is at most 9+9+1=19, so carry ≤ 1 always).
8. cur.next = ListNode(total % 10) — result digit is the units part.
9. cur = cur.next — advance tail.
10. if l1: l1 = l1.next — only advance if not exhausted (safe guard).
11. return dummy.next — dummy itself has value 0 and is not part of the result.

Watch it happen, frame by frame

l1: 2 → 4 → 3 (342) | l2: 5 → 6 → 4 (465) | Expected: 7 → 0 → 8 (807)

carry=0, cur=dummy

Iter 1 (units column):
  val1=2, val2=5, total=7, carry=0
  Append node(7). dummy→7
  l1=4→3, l2=6→4. cur=node(7)

Iter 2 (tens column):
  val1=4, val2=6, total=10, carry=1
  Append node(0). dummy→7→0
  l1=3, l2=4. cur=node(0)

Iter 3 (hundreds column):
  val1=3, val2=4, total=7+1(carry)=8, carry=0
  Append node(8). dummy→7→0→8
  l1=None, l2=None. cur=node(8)

Iter 4 check: l1=None, l2=None, carry=0 → exit loop.

return dummy.next = node(7) → 7→0→8  ✅

Edge case: carry after last digits

l1: 9 → 9 (99) | l2: 1 (1) | Expected: 0 → 0 → 1 (100)

carry=0

Iter 1: val1=9, val2=1, total=10, carry=1. Append 0. l1=9, l2=None.
Iter 2: val1=9, val2=0, total=9+1=10, carry=1. Append 0. l1=None, l2=None.
Iter 3: l1=None, l2=None, carry=1. val1=0, val2=0, total=1, carry=0. Append 1.
Iter 4: all None, carry=0 → exit.

Result: 0→0→1  ✅  (represents 100)

The or carry in the loop condition is exactly what catches this final node.

Variant: digits stored in forward order (LC #445)

Add Two Numbers II (LC #445): same problem but l1 = 3 → 4 → 2 represents 342 (head = most significant digit). You cannot add head-to-head because the carries flow from right to left but the list runs left-to-right.

Strategy — stack:

def addTwoNumbersII(l1, l2):
    s1, s2 = [], []
    while l1: s1.append(l1.val); l1 = l1.next
    while l2: s2.append(l2.val); l2 = l2.next

    carry = 0
    head  = None
    while s1 or s2 or carry:
        val1  = s1.pop() if s1 else 0
        val2  = s2.pop() if s2 else 0
        total = val1 + val2 + carry
        carry = total // 10
        node  = ListNode(total % 10)
        node.next = head    # prepend to result (result builds right-to-left)
        head      = node

    return head

Key difference: we pop from stacks (so we process least-significant digits first, just like LC #2), and we prepend each new node to build the result in forward order.

Why not reverse the lists? We could reverse both inputs, run the LC #2 solution, then reverse the result — three O(n) passes. The stack approach also does three O(n) passes but keeps it as one function and avoids mutating the input lists.

Common traps

dummy = ListNode(0); cur = dummy; carry = 0
while l1 or l2 or carry:
    v1 = l1.val if l1 else 0
    v2 = l2.val if l2 else 0
    s  = v1 + v2 + carry
    carry, cur.next = s // 10, ListNode(s % 10)
    cur = cur.next
    if l1: l1 = l1.next
    if l2: l2 = l2.next
return dummy.next

Check yourself

Practice problems

Next up: Clone a List with Random Pointers — where each node also has a random pointer to any node in the list (or None), requiring you to deep-copy both the next chain and the random links without confusing original and cloned nodes.