A ledger service stores each invoice total as a singly linked column of digits, ones place at the head — the same order a clerk adds a paper column from the right. Nightly close needs two invoice totals added and returned as another column in that form. The intern packed both lists into a long, added, and unpacked. Twelve-digit staging invoices matched. A forty-digit production total wrapped to a negative. Switching to BigInteger patched overflow. The numbers matched. The lists had already been the addition encoding; parsing threw that away.

Add Two Numbers is schoolbook addition: ones at the head, a carry toward higher places. The linked list post owns splice, dummy nodes, and why get(i) walks. Merge two sorted lists already used a dummy so the first splice had a predecessor. Here we reuse that habit. We only care about digit plus digit plus carry.

The problem

Given the heads of two non-negative integers stored as singly linked lists, each node one digit, ones place at the head. Return their sum as a new list in the same reverse-digit form. The lists may differ in length. A leftover carry may need one extra node.

a = 2 → 4 → 3        (342)
b = 5 → 6 → 4        (465)
sum = 7 → 0 → 8      (807)

a = 0
b = 0
sum = 0

a = 9 → 9 → 9        (999)
b = 1                (1)
sum = 0 → 0 → 0 → 1  (1000)

A node is the usual two fields:

final class ListNode {
    int val;
    ListNode next;

    ListNode(int val) {
        this.val = val;
    }
}

Note: Reverse order is the gift — addition already starts at the ones place, so you walk from the head. A missing digit is 0. Merge attaches an unused tail in one write; this problem cannot, because leftover digits still meet the carry.

Parse, add, rebuild is the honest brute

Walk each list, rebuild the integer, add, then allocate a fresh chain from the sum. The numbers come out right until they do not.

ListNode addByParsing(ListNode a, ListNode b) {
    return fromLong(toLong(a) + toLong(b));
}

long toLong(ListNode head) {
    long n = 0;
    long place = 1;
    for (ListNode p = head; p != null; p = p.next) {
        n += (long) p.val * place;
        place *= 10;
    }
    return n;
}

ListNode fromLong(long n) {
    ListNode dummy = new ListNode(0);
    ListNode tail = dummy;
    do {
        tail.next = new ListNode((int) (n % 10));
        tail = tail.next;
        n /= 10;
    } while (n > 0);
    return dummy.next;
}

At a dozen digits this is a rounding error. At twenty, place *= 10 wraps and the sum is garbage. BigInteger patches overflow and still parses an encoding the lists already were — reverse digits, ready to add from the head.

Dummy head, then digit plus digit plus carry

A dummy head, same habit as merge: the first written digit has a predecessor, so a one-node 0 and a four-node 1000 share the loop. Keep tail on the last written digit. Keep carry. Each step, a missing list contributes 0. Write sum % 10, keep sum / 10. Advance whichever list still has a node. The loop runs while either list remains or carry is still live.

Walk 2 → 4 → 3 against 5 → 6 → 4:

start: dummy → null, tail=dummy, carry=0, a=2, b=5

2+5+0 = 7   digit=7 carry=0   dummy → 7
4+6+0 = 10  digit=0 carry=1   dummy → 7 → 0
3+4+1 = 8   digit=8 carry=0   dummy → 7 → 0 → 8

both null, carry 0 → return dummy.next

Walk 9 → 9 → 9 against 1 — unequal length and a leftover carry are the same loop, not a special case:

start: dummy → null, tail=dummy, carry=0, a=9, b=1

9+1+0 = 10  dummy → 0,           carry=1
9+0+1 = 10  dummy → 0 → 0,       carry=1
9+0+1 = 10  dummy → 0 → 0 → 0,   carry=1
0+0+1 = 1   dummy → 0 → 0 → 0 → 1, carry=0

return dummy.next

The Java is that walk. You allocate new nodes because 4 + 6 is a new 0 and a carry, not a reuse of either input.

ListNode addTwoNumbers(ListNode a, ListNode b) {
    ListNode dummy = new ListNode(0);
    ListNode tail = dummy;
    int carry = 0;
    while (a != null || b != null || carry != 0) {
        int x = (a != null) ? a.val : 0;
        int y = (b != null) ? b.val : 0;
        int sum = x + y + carry;
        tail.next = new ListNode(sum % 10);
        tail = tail.next;
        carry = sum / 10;
        if (a != null) {
            a = a.next;
        }
        if (b != null) {
            b = b.next;
        }
    }
    return dummy.next;
}

Time is O(max(m, n)) — one pass, one new node per output digit. Space is O(1) besides the output list and the dummy. Digit plus carry is at most 19, so int is enough.

Stopping when both lists end, before carry is zero, drops the extra digit. 999 + 1 becomes 0 → 0 → 0. Splicing a leftover chain the way merge does is the same bug: remaining nines still have to meet the carry.

Note: A missing digit is 0, not a skip of that list. Empty-looking 0 + 0 needs no special case: one iteration writes 0, carry dies, you return dummy.next.

What interviewers usually poke next

  • Most-significant digit at the head. Reverse both, then this walk, then reverse the result — or recurse to the tails and add on the way back. The reverse-digit prompt is the easier encoding; say why.
  • Mutate the longer list in place. Possible; length mismatch and a leftover carry that needs a new node make dummy-plus-new-chain the default.
  • Plus One. One list, same carry walk. A cousin, not this prompt.
  • Do it with BigInteger. Correct numbers, wrong encoding, hides the carry. Say why the digit walk is the bill they asked for.

You are done with this problem when you can add 999 + 1 on a whiteboard and produce the extra node without a special case, and you can name why a leftover list cannot be spliced the way merge splices it.