Add Two Numbers — Carry Simulation on Reversed Linked Lists

Problem Statement#

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list. You may assume the two numbers do not have leading zeros, except the number 0 itself.

Constraints:

• The number of nodes in each linked list is in the range [1, 100]
• 0 <= Node.val <= 9
• It is guaranteed that the list represents a number that does not have leading zeros

Example 1:

Input:  l1 = [2,4,3], l2 = [5,6,4]
Output: [7,0,8]
Explanation: 342 + 465 = 807. Digits reversed: 7->0->8.

Example 2:

Input:  l1 = [0], l2 = [0]
Output: [0]

Example 3:

Input:  l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
Output: [8,9,9,9,0,0,0,1]
Explanation: 9999999 + 9999 = 10009998. Reversed: 8->9->9->9->0->0->0->1.

Why This Problem Matters#

Add Two Numbers (LeetCode 2) is the second problem on LeetCode and one of the most-asked problems in all of software engineering interviews. Amazon, Google, and Microsoft use it because it tests a specific kind of simulation skill: translating a familiar manual process (elementary school addition with carry) into clean pointer-based code.

The problem appears simple but has precisely calibrated edge cases: what happens when one list is longer than the other? What happens if there's a carry at the very end (e.g., 9 + 9 = 18, so you create an extra node)? These are the cases that trip up rushed solutions.

At a deeper level, this problem teaches you that linked lists can represent mathematical objects and that classical algorithms (digit-by-digit addition from LSB to MSB) map naturally onto linked list traversal when the digits are stored in reverse. This insight shows up again in Add Two Numbers II (LC 445), where digits are in forward order — requiring you to either reverse them or use stacks.

Understanding carry propagation cleanly also prepares you for problems like Multiply Strings (LC 43), Add Binary (LC 67), and Plus One (LC 66).

The Core Insight#

Walk both lists simultaneously from the least significant digit (head) to the most significant. At each position, compute total = l1_digit + l2_digit + carry. The result digit for this position is total % 10, and the carry for the next position is total // 10.

The dummy head simplifies building the output list: you never need to initialize the head specially — every node is built the same way.

The loop condition while l1 or l2 or carry is critical: it handles three scenarios:

• Both lists have nodes
• One list is exhausted but the other continues
• Both lists are exhausted but there's still a carry (e.g., 999 + 1 = 1000)

Visual Dry Run#

Input: l1 = 2 -> 4 -> 3 (represents 342), l2 = 5 -> 6 -> 4 (represents 465)

Expected: 342 + 465 = 807 → output 7 -> 0 -> 8

Output nodes: 7 -> 0 -> 8. Return dummy.next = 7. Correct.

Carry at end case: l1 = 9 -> 9, l2 = 1 (99 + 1 = 100)

Output: 0 -> 0 -> 1 (represents 100). Correct.

Solution (Optimal)#

Python#

def addTwoNumbers(l1, l2):
    dummy = ListNode(0)  # sentinel for result list
    curr = dummy
    carry = 0
 
    while l1 or l2 or carry:
        # Get current digits (0 if list exhausted)
        a = l1.val if l1 else 0
        b = l2.val if l2 else 0
 
        # Compute sum with carry
        total = a + b + carry
        carry = total // 10      # carry for next position
        digit = total % 10       # digit for this position
 
        # Append new node to result
        curr.next = ListNode(digit)
        curr = curr.next
 
        # Advance input lists
        if l1: l1 = l1.next
        if l2: l2 = l2.next
 
    return dummy.next

Time complexity: O(max(m, n)) — process every digit of both lists.

Space complexity: O(max(m, n)) — output list has max(m, n) + 1 nodes (the +1 for potential carry).

JavaScript#

var addTwoNumbers = function(l1, l2) {
    const dummy = new ListNode(0);
    let curr = dummy;
    let carry = 0;
 
    while (l1 !== null || l2 !== null || carry !== 0) {
        const a = l1 !== null ? l1.val : 0;
        const b = l2 !== null ? l2.val : 0;
 
        const total = a + b + carry;
        carry = Math.floor(total / 10);
 
        curr.next = new ListNode(total % 10);
        curr = curr.next;
 
        if (l1 !== null) l1 = l1.next;
        if (l2 !== null) l2 = l2.next;
    }
 
    return dummy.next;
};

Complexity:

Common Mistakes#

1. Not including carry in the while loop condition. If l1 = [5] and l2 = [5], total = 10, digit = 0, carry = 1. After one iteration, l1 and l2 are both None. If the condition is while l1 or l2, the loop exits without processing the carry — you'd return [0] instead of [0, 1] (which is 10).

2. Not using 0 when a list is exhausted. After l1 or l2 reaches None, its "digit" is 0. a = l1.val if l1 else 0 handles this. Without the guard, l1.val crashes when l1 is None.

3. Using divmod incorrectly. In Python, carry, digit = divmod(total, 10) returns (quotient, remainder) = (carry, digit). This is correct. Some candidates write divmod(total, 10) and unpack in the wrong order.

4. Forgetting to advance l1 and l2. After creating the result node, advance both input list pointers. Forgetting this creates an infinite loop as the same digits are processed repeatedly.

5. Not using a dummy head. Without dummy, you need to initialize the result head: "is the first node from l1 or l2 or a carry node?" The dummy eliminates this branching — all nodes are created uniformly in the loop.

Interview Tips#

1. Map to grade-school addition: "I'll simulate the same process I'd use to add numbers by hand: go digit by digit from LSB to MSB, track the carry."

2. State the carry condition explicitly: "The loop must continue as long as there are digits in either list OR there's a remaining carry. The carry-only case handles things like 999 + 1."

3. Walk through the carry-propagation example: l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9] — show that the result has one more digit than the longer input.

4. Mention the follow-up: "Add Two Numbers II (LC 445) stores digits in forward order — the same algorithm but you need to reverse first (or use stacks to process from LSB)."

5. Code cleanly: The a = l1.val if l1 else 0 pattern is idiomatic Python — use it. In Java/JavaScript, use the ternary form.

Follow-up Questions#

Q: What if the digits are stored in forward order (most significant first)? That's LeetCode 445 (Add Two Numbers II). You'd push both lists to stacks, then pop from both stacks to process digits from LSB to MSB. The same carry logic applies.

Q: Can you do it without creating new nodes (in-place)? You'd reuse one of the input lists (the longer one) and store result digits in it. You'd still create extra nodes if the result is longer than the input. Not commonly expected in interviews.

Q: What if numbers can have leading zeros? The problem guarantees no leading zeros except "0" itself. If they were allowed, the algorithm would still work correctly (leading zeros in the reversed representation appear at the end and add zero contribution).

Q: What's the maximum result length? If both lists have n digits and all digits are 9, the result has n+1 digits (e.g., 999...9 + 999...9 = 1999...8). So the output is at most max(m, n) + 1 nodes.

Q: How does this generalize to adding k numbers? For k numbers, use the same digit-by-digit approach but sum k digits plus carry at each position. Carry can be up to k at any position. The algorithm structure is identical.

Key Takeaways#

• The loop condition while l1 or l2 or carry handles all cases: unequal lengths and trailing carry after both lists exhaust.
• Use a = l1.val if l1 else 0 to treat exhausted lists as contributing 0.
• carry = total // 10, digit = total % 10 — elementary school addition.
• The dummy head sentinel makes result-list construction uniform — always return dummy.next.
• Output length is at most max(m, n) + 1 for a final carry node.
• The digits-reversed storage means the head is the least significant digit — iterate forward to process LSB to MSB.