Linked List Arithmetic

Description

Linked-list arithmetic adds numbers stored one digit per node, the way you add on paper: digit by digit from the ones place, carrying into the next column. When the lists hold the digits ones-first, one walk does it. When they hold them in normal reading order, you need a way to reach the ones digits first: stacks, or reversing the lists. It's a small model of how arbitrary-precision numbers work.

We'll go from simple to more technical:

1. The pattern: add digit by digit, carrying, until both lists and the carry run out.
2. A second flavor: forward-order digits, using stacks and prepending.
3. Where digit-by-digit arithmetic runs in production (bignum libraries, money).
4. The bugs: a dropped final carry, unequal lengths, the wrong build direction.

The approach

When each list stores its number ones digit first, walking both lists from the head is exactly adding by hand from the right. In each column, add the two digits and the carry. Write down the last digit of the sum, and carry the rest into the next column. A list that has run out counts as 0. Keep going while either list or the carry remains.

Adding 958 and 67, stored as 8 -> 5 -> 9 and 7 -> 6:

The result is 5 -> 2 -> 0 -> 1, which is 1025. The last row exists only because of the carry.

ListNode dummy = new ListNode(0);
ListNode tail = dummy;
int carry = 0;
while (l1 != null || l2 != null || carry != 0) {
    int sum = carry;
    if (l1 != null) { sum += l1.val; l1 = l1.next; }
    if (l2 != null) { sum += l2.val; l2 = l2.next; }
    carry = sum / 10;
    tail.next = new ListNode(sum % 10);
    tail = tail.next;
}
return dummy.next;

def add_two_numbers(l1: ListNode | None, l2: ListNode | None) -> ListNode | None:
    dummy = ListNode(0)
    tail = dummy
    carry = 0
    while l1 is not None or l2 is not None or carry:
        total = carry
        if l1 is not None:
            total += l1.val
            l1 = l1.next
        if l2 is not None:
            total += l2.val
            l2 = l2.next
        carry = total // 10
        tail.next = ListNode(total % 10)
        tail = tail.next
    return dummy.next

Each part of the loop condition handles a case. Checking both lists handles unequal lengths. Checking the carry handles a final carry, like the 1 above. Drop any one, and the code is wrong only on those inputs, which is how such bugs survive casual testing.

A second flavor: forward-order digits need a stack

Now say the digits are stored in normal reading order: 9 -> 5 -> 8 and 6 -> 7. The carry still has to start from the ones digits, but they're at the ends of the lists, and a singly linked list can't be walked backward. So push each list's digits onto a stack. Popping then gives the ones digits first. The result, though, must come out in reading order. So each new digit is put at the front of the result, not the end:

Deque<Integer> s1 = new ArrayDeque<>(), s2 = new ArrayDeque<>();
while (l1 != null) { s1.push(l1.val); l1 = l1.next; }
while (l2 != null) { s2.push(l2.val); l2 = l2.next; }

int carry = 0;
ListNode result = null;
while (!s1.isEmpty() || !s2.isEmpty() || carry != 0) {
    int sum = carry + (s1.isEmpty() ? 0 : s1.pop()) + (s2.isEmpty() ? 0 : s2.pop());
    carry = sum / 10;
    ListNode node = new ListNode(sum % 10);
    node.next = result;     // PREPEND - result must stay in most-significant-first order
    result = node;
}
return result;

def add_two_numbers(l1: ListNode | None, l2: ListNode | None) -> ListNode | None:
    s1, s2 = [], []                  # Python lists work as stacks: append / pop
    for node, stack in ((l1, s1), (l2, s2)):
        while node is not None:
            stack.append(node.val)
            node = node.next
    carry, result = 0, None
    while s1 or s2 or carry:
        total = carry + (s1.pop() if s1 else 0) + (s2.pop() if s2 else 0)
        carry = total // 10
        node = ListNode(total % 10)
        node.next = result           # PREPEND - result must stay in most-significant-first order
        result = node
    return result

The digits come out 5, 2, 0, 1, and prepending each one gives 1 -> 0 -> 2 -> 5. The first digit computed ends up last, which is exactly reading order.

Where you'll see it

Big-number libraries and money calculations that can't use floating point add digit by digit with a carry, just like this. They usually store digits in an array, ones first, so the carry can flow in the natural direction.

Which tool for which job?

Common mistakes

Check yourself

Try to answer before opening each one - recalling beats re-reading.

1. Why does the loop keep going while carry != 0, even after both lists are done?

2. Why do reading-order digits need a stack when ones-first digits don't?

3. Why prepend each new digit instead of appending it?

Key takeaways

• Loop while either list or the carry remains. Each part of that condition handles a real case.
• The carry flows from the ones digit up. Ones-first lists already walk that way.
• Reading-order lists need a stack (or a reversal) to reach the ones digits first.
• When digits are computed in the opposite order to the output, prepend each one.
• Both versions take O(max(n, m)) time; the stack version also needs O(n + m) extra space.