Problem Statement

• 445. Add Two Numbers II

You are given two non-empty linked lists representing two non-negative integers. The most significant digit comes first 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 contain any leading zero, except the number 0 itself.

Example:

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

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

Algorithm Overview

The key insight is that addition is performed from right to left (least significant digit first), but our linked lists are given from left to right (most significant digit first). We need to reverse the processing order.

Steps:

1. Push all digits onto stacks - This reverses the order so we can process from least significant digit
2. Pop and add digits with carry handling - Process digits from right to left, maintaining carry
3. Build result list from front - Since we're processing backwards, we prepend each new digit to the result

Implementation:

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    Stack<Integer> stack1 = new Stack<>();
    Stack<Integer> stack2 = new Stack<>();

    // Step 1: Push all digits onto stacks
    while (l1 != null) {
        stack1.push(l1.val);
        l1 = l1.next;
    }
    while (l2 != null) {
        stack2.push(l2.val);
        l2 = l2.next;
    }

    ListNode result = null;
    int carry = 0;

    // Step 2: Pop and add digits with carry
    while (!stack1.isEmpty() || !stack2.isEmpty() || carry > 0) {
        int sum = carry;
        if (!stack1.isEmpty()) sum += stack1.pop();
        if (!stack2.isEmpty()) sum += stack2.pop();

        carry = sum / 10;

        // Step 3: Build result by prepending
        ListNode newNode = new ListNode(sum % 10);
        newNode.next = result;
        result = newNode;
    }

    return result;
}

Key Points:

• Stacks naturally reverse the digit order for processing
• We handle different list lengths by checking if stacks are empty
• Result is built by prepending each digit (since we process backwards)
• Carry propagation works exactly like manual addition

Complexity Analysis

Time Complexity: O(max(m, n))

• m = length of first linked list, n = length of second linked list
• We traverse each list once to fill the stacks: O(m + n)
• We process digits once during addition: O(max(m, n))
• Overall: O(m + n) = O(max(m, n)) since m, n ≥ 1

Space Complexity: O(m + n)

• Two stacks store all digits from both lists: O(m + n)
• Result list contains at most max(m, n) + 1 nodes: O(max(m, n))
• Overall: O(m + n)

Trade-offs:

• Pros: Simple, intuitive, handles edge cases naturally
• Cons: Uses extra space for stacks (can be avoided with list reversal approach)
• Alternative: Reverse both lists, add normally, then reverse result (O(1) extra space but more complex)

The stack approach is preferred for its clarity and ease of implementation, making it ideal for coding interviews despite the extra space usage.