LeetCode 2 – Add Two Numbers | Love Me Some Coding

Add Two Numbers is elementary-school long addition wearing a linked list costume. The one design decision that separates a clean solution from a fiddly one is the dummy head, and the one bug everybody writes at least once is forgetting the final carry.

The problem

Two non-empty linked lists represent two non-negative integers. The digits are stored in reverse order — the ones digit is at the head — and each node holds a single digit. Add the two numbers and return the sum as a linked list in the same format.

Input:  l1 = 2 -> 4 -> 3      (the number 342)
        l2 = 5 -> 6 -> 4      (the number 465)
Output:      7 -> 0 -> 8      (the number 807)

Input:  l1 = 9 -> 9 -> 9
        l2 = 1
Output:      0 -> 0 -> 0 -> 1  (999 + 1 = 1000 — the answer is longer than either input)

Why reverse order is a gift, not an obstacle

Reverse order is the whole reason this problem is Medium and not Hard. Addition starts at the ones digit and carries left — which is exactly the direction a singly linked list can be walked. Both lists are already pointing at the digit you need first, and the carry travels the same way you do.

Do not be tempted to convert the lists to integers, add, and convert back. The test cases include inputs with a hundred digits; that approach overflows a long immediately. In Python it would technically work, and it is still the wrong answer to give — the interviewer is asking for the digit-by-digit walk.

The idea

Walk both lists together, one digit at a time. At each step the sum is carry + l1.val + l2.val, treating a list that has already run out as contributing nothing. The new node gets sum % 10, and sum / 10 becomes the carry for the next step.

Two details do all the work:

A dummy head. Building a list means the first node is a special case — there is no previous node to attach it to. Allocating one throwaway node up front removes that case entirely, and dummy.next is the real answer at the end.
carry != 0 in the loop condition. When both lists are exhausted there can still be a carry left over, and it needs one more node. Putting it in the condition instead of writing a separate if after the loop is what makes 999 + 1 work without any extra code.

Java

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0);   // throwaway node; the answer is dummy.next
        ListNode tail = dummy;
        int carry = 0;

        // The carry in the condition is what gives 999 + 1 its fourth node.
        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;                        // sum is at most 9 + 9 + 1 = 19,
            tail.next = new ListNode(sum % 10);      // so the carry is always 0 or 1
            tail = tail.next;
        }

        return dummy.next;
    }
}

Python

class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        dummy = tail = ListNode(0)
        carry = 0

        while l1 or l2 or carry:
            total = carry
            if l1:
                total += l1.val
                l1 = l1.next
            if l2:
                total += l2.val
                l2 = l2.next

            carry, digit = divmod(total, 10)
            tail.next = ListNode(digit)
            tail = tail.next

        return dummy.next

Complexity

O(max(m, n)) time — one pass, one node visited per digit of the longer input. O(max(m, n)) space for the result list, which is unavoidable since the answer has that many nodes; the algorithm itself uses O(1) auxiliary space.

The follow-up you should expect

Add Two Numbers II (LeetCode 445) is the same problem with the digits stored in forward order, so the ones digit is at the tail and the carry has to travel against the direction you can walk. Three ways out, in the order an interviewer likes them:

Push both lists onto stacks, then pop — the stacks reverse the traversal for you, and building the result by prepending nodes puts it back in forward order.
Reverse both inputs, run the solution above, reverse the result. Correct, but it mutates the inputs, so say so before doing it.
Recurse to the end and add on the way back up, after padding the shorter list.

What the interviewer is checking

That you build with a dummy head rather than special-casing the first node.
That the trailing carry produces a node — [9,9,9] + [1] is the test case that catches this.
That unequal lengths need no padding pass, just a null check per list.
That you did not convert to an integer and hope the input stays short.