Add Two Numbers (Digits in Reverse)

Adding two numbers digit by digit in reverse order is a great warm‑up for handling arbitrary‑precision arithmetic in systems that store values across linked structures—think big‑integer libraries or chaining financial transactions. It tests your ability to traverse linked lists, manage carries, and build a new list on the fly.

Problem Statement

You’re given two non‑empty singly linked lists l1 and l2 representing two non-negative integers. The digits are stored in reverse order, and each node contains a single digit. Add the two numbers and return the sum as a linked list, also in reverse order. You may assume the two numbers do not contain leading zeros, except the number zero itself.

class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}

// Signature:
public ListNode addTwoNumbers(ListNode l1, ListNode l2);

1. Clarify Requirements Before Jumping Into Code

I’ll ask a few clarifying questions:

• Digits are 0–9, stored least significant first.

• Lists can be different lengths.

• We must handle a final carry node if sum exceeds existing length.

• Empty input lists won’t happen—always at least one node per list.

• Aim for O(max(m,n)) time and O(max(m,n)) extra space for the result.

2. Identify the Category of the Question

This is a linked‑list arithmetic problem that combines:

• Two-pointer traversal (walking both lists in tandem)

• Digit‑by‑digit addition with carry (grade‑school algorithm)

• List construction (building the result as we go)

Common patterns in this category include adding numbers stored in lists, merging lists, and handling varying lengths with default values.

3. Consider a Brute‑Force Approach to Understand the Problem

A brute-force idea is to convert each list to a full integer (or string), parse it into a built‑in big‑integer, add them, then convert the result back into a reversed linked list.

• Time Complexity: O(m + n + k) where k is length of result’s digits

• Space Complexity: O(m + n + k) for strings or BigInteger representation

• Drawbacks: Relies on library types, risks overflow in fixed-size integers, and obscures linked-list logic.

4. Brainstorm More Solutions

I want to work directly on the lists. Possibilities:

• Two‑pass for alignment: First measure lengths, pad the shorter with zeros, then add recursively with carry. That’s complex pointer math and recursion overhead.

• Stack-based addition: Push digits of both lists onto stacks, pop and add with carry, build result by pushing new nodes. Uses O(m + n) space for stacks.

• Single‑pass carry addition: Maintain a dummy head and a current pointer. Keep a carry variable. While either list has nodes or carry>0, read each list’s digit (or 0), sum with carry, create a new node with sum % 10, update carry, advance pointers. This is clean, O(max(m,n)) time, O(max(m,n)) space for result, and no extra stacks or recursion.

To derive the single‑pass solution live, I’d think: I need to simulate hand‑addition from least significant digit upward. The lists already give me LSB first, so I can just walk both in lockstep, adding 0 when one runs out. I’ll carry any overflow into the next digit. A dummy head simplifies list construction.

5. Discuss Trade‑Offs Between Your Solutions

Approach	Time	Space	Pros	Cons
Convert to BigInteger	O(m + n + k)	O(m + n + k)	Leverages library, minimal pointer code	Overflow risk, hides core logic
Stack-based addition	O(m + n)	O(m + n)	Clear separation of digit retrieval & add	Extra O(m+n) stack space
Single‑pass carry addition	O(max(m,n))	O(max(m,n))	Direct, one-pass, no extra data structures	Need careful carry and pointer code

Single‑pass addition is straightforward, maps exactly to the problem requirements, and uses only O(1) extra variables.

6. Write Pseudocode to Structure Your Thoughts

function addTwoNumbers(l1, l2):
  dummy = new ListNode(0)
  current = dummy
  carry = 0

  while l1 != null or l2 != null or carry != 0:
    val1 = (l1 != null) ? l1.val : 0
    val2 = (l2 != null) ? l2.val : 0
    sum = val1 + val2 + carry
    carry = sum / 10
    current.next = new ListNode(sum % 10)
    current = current.next

    if l1 != null: l1 = l1.next
    if l2 != null: l2 = l2.next

  return dummy.next

7. Consider Edge Cases

• Both lists single node summing < 10 → one‑node result

• Both lists single node summing ≥ 10 → two‑node result with carry

• Different lengths (e.g. [9,9] + [1]) → handles trailing carry

• Zeros (e.g. [0] + [0]) → returns [0]

• Long trailing carry (e.g. [9,9,9] + [1]) → extends result correctly

8. Write Full Code Syntax

class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}

public class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0);
        ListNode current = dummy;
        int carry = 0;

        while (l1 != null || l2 != null || carry != 0) {
            int val1 = (l1 != null) ? l1.val : 0;
            int val2 = (l2 != null) ? l2.val : 0;
            int sum = val1 + val2 + carry;
            carry = sum / 10;

            current.next = new ListNode(sum % 10);
            current = current.next;

            if (l1 != null) l1 = l1.next;
            if (l2 != null) l2 = l2.next;
        }

        return dummy.next;
    }
}

9. Test Your Code

public static void main(String[] args) {
    Solution sol = new Solution();

    // Helpers buildList(...) and toArray(...) omitted for brevity

    // Test 1: simple no carry
    assert Arrays.equals(
      sol.addTwoNumbers(buildList(2,4,3), buildList(5,6,4)).toArray(),
      new int[]{7,0,8}
    );  // 342 + 465 = 807

    // Test 2: single-digit with carry
    assert Arrays.equals(
      sol.addTwoNumbers(buildList(5), buildList(7)).toArray(),
      new int[]{2,1}
    );  // 5 + 7 = 12

    // Test 3: different lengths
    assert Arrays.equals(
      sol.addTwoNumbers(buildList(9,9), buildList(1)).toArray(),
      new int[]{0,0,1}
    );  // 99 + 1 = 100

    // Test 4: zeros
    assert Arrays.equals(
      sol.addTwoNumbers(buildList(0), buildList(0)).toArray(),
      new int[]{0}
    );

    // Test 5: long carry chain
    assert Arrays.equals(
      sol.addTwoNumbers(buildList(9,9,9), buildList(1)).toArray(),
      new int[]{0,0,0,1}
    );  // 999 + 1 = 1000

    System.out.println("All tests passed!");
}

10. Key Lessons to Remember for Future Questions

• Simulate hand‑addition: digit-by-digit with carry, exactly like on paper.

• Dummy-head technique simplifies list construction and avoids special-case head assignment.

• Checking carry in the loop condition ensures final carry is handled.

• Handling null list nodes by defaulting to zero keeps logic uniform.

• Writing clear pseudocode for digit retrieval, sum, carry, and pointer moves prevents off-by-one errors.

• Testing both equal‑length and unequal‑length cases, as well as trailing carries, ensures robustness.

Good Luck and Happy Coding!