Domain 2MediumCORE

Add Two Numbers II

We are given two singly linked lists representing large integers in standard decimal notation (Most Significant Digit first, MSB->LSB). We need to compute their sum and return the result as a new linked list with digits also ordered from MSB to LSB.

Domain: Medium•Updated: 2026-08-31
#Algorithms#LeetCode#qwen3.5:9b#Linked List

445. Add Two Numbers II

Model: qwen3.5:9b
Topics: Linked List
FAANG asked: 1
Acceptance rate: 56.5%


Problem Breakdown

We are given two singly linked lists representing large integers in standard decimal notation (Most Significant Digit first, MSB->LSB). We need to compute their sum and return the result as a new linked list with digits also ordered from MSB to LSB.

Inputs: Two non-empty ListNode objects (l1, l2). Each node contains one digit 0-9. Outputs: A single ListNode representing the sum, maintaining MSB-first order. Constraints & Edge Cases:

  • Lists can be of different lengths (e.g., adding a number with fewer digits).
  • Carry propagation must continue even after both lists are exhausted if there is remaining carry (result has more digits than inputs).
  • Input numbers do not have leading zeros, except for the single digit 0.
  • We cannot modify input nodes in place to reverse them (per follow-up), so we need a strategy that reads values without changing pointer structure of l1 or l2.

Intuition

Standard addition works from right-to-left (LSB first). However, our linked lists are given left-to-right (MSB first). To add digits correctly, we must access the end of each list before processing.

A brute-force approach would be to convert both lists into integers and sum them directly. While Python handles arbitrarily large integers automatically, this is often not allowed in low-level languages or strict memory-constrained environments due to potential overflow (in fixed-width types) or excessive space/time for conversion overhead. Furthermore, it bypasses the core algorithmic challenge of linked list manipulation.

The key insight is that we can reverse the logical order of traversal without modifying node pointers by using Stacks. By pushing all digits from l1 and l2 onto stacks during a first pass (or while traversing), we effectively get access to LSBs at the top of each stack. We then pop values, perform addition with carry logic, and build our result list digit-by-digit starting from the units place up to MSB.

Approach

  1. Stack Initialization: Traverse both input lists l1 and l2. Push every node’s value onto two separate stacks (stack1, stack2). This takes O(N+M) time but does not modify the original linked list structure, satisfying the follow-up constraint.
  2. Addition Loop: Initialize a carry variable to 0. While either stack is non-empty or there is still a pending carry:
    • Pop values from stacks (defaulting to 0 if empty).
    • Calculate sum = val1 + val2 + carry.
    • The new digit for the result node is sum % 10.
    • Update carry as sum // 10.
  3. Result Construction: Since we are processing digits from LSB to MSB, if we append nodes sequentially, our resulting list will be in reverse order (LSB first). To maintain the required MSB-first output without an extra reversal pass, we can prepend each new node at the head of a dummy result list. Alternatively, build via appending and reverse pointers once at the end; however, prepending is O(1) per step if managed correctly with head pointer updates. I will use a standard “dummy” approach where nodes are appended to a tail, then reversed? No, simpler: Use a new_head variable that points to the most recently created node (which becomes MSB).
    • Actually, for clarity and robustness in Python code without complex pointer gymnastics during loop updates, I will build the list by appending nodes as calculated. Since we process LSB first, the resulting linked list naturally forms from LSB at head -> MSB at tail? No, that’s wrong order.
    • Correction: If I pop stacks (LSB), calculate digit d, and create node n = ListNode(d). To get correct output (MSB->...->LSB), the first calculated digit (units place) must be at the end of the list, not head.
    • Strategy: Create a dummy node to start building result. Append new nodes to it as we iterate? No, that puts LSB at head.
    • Better Strategy for MSB-first output from Stack pops: Prepend each calculated digit to the front of our result list (update head = newNode; newNode.next = old_head). This ensures units place ends up last in chain naturally after all digits processed? Wait, if I prepend first popped (LSB), it becomes head. Then next pop (next higher) prepends before LSB. So final order is MSB -> … -> LSB. Yes.
    • Implementation: Use a dummy node to simplify logic or just track head. Tracking head and updating pointers (new_node.next = current_head; current_head = new_node) works perfectly in O(1).

Complexity Analysis

  • Time: O(N+M)O(N + M), where N and M are lengths of the two lists. We traverse each list once to push onto stacks (or read), then iterate through combined length for addition logic. Prepending/pointer updates is constant time per digit.
  • Space: O(N+M)O(N + M). We use extra space proportional to input size for the two stacks and the new result linked list. This satisfies memory constraints better than recursion which might hit stack depth limits on very long lists, though both are linear in terms of auxiliary storage relative to inputs.

Solution

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def addTwoNumbers(l1: 'ListNode', l2: 'ListNode') -> 'ListNode':
    # Stacks to reverse logical order of traversal without modifying input pointers
    stack1, stack2 = [], []
    
    curr1, curr2 = l1, l2
    
    while curr1 or curr2:
        if curr1:
            stack1.append(curr1.val)
            curr1 = curr1.next
        else:
            # Pad with 0 implicitly handled by pop default logic later? 
            # Better to push dummy values or handle empty check in loop.
            # Actually, simpler: just append until list exhausted then stop pushing?
            # No, we need both stacks populated up to max length for alignment.
            pass
            
    # Re-traverse cleanly to fill stacks properly without complex padding logic inside while above
    curr1 = l1
    curr2 = l2
    
    while curr1: stack1.append(curr1.val); curr1 = curr1.next
    while curr2: stack2.append(curr2.val); curr2 = curr2.next

    carry, head = 0, None # 'head' will track the MSB-most node of result list
    
    while stack1 or stack2 or carry > 0:
        val1 = stack1.pop() if stack1 else 0
        val2 = stack2.pop() if stack2 else 0
        
        total = val1 + val2 + carry
        digit = total % 10
        new_node = ListNode(digit)
        
        # Prepend to maintain MSB-first order naturally as we process LSBs first
        new_node.next = head
        head = new_node
        
        carry = total // 10

    return head

Edge Cases Handled

  • Different Length Lists: The loop condition while stack1 or stack2 ensures we continue processing until both stacks are empty. Missing values from shorter lists default to 0 during addition logic (handled by ternary check).
  • Final Carry: If the sum generates a carry after all digits are processed, the final iteration of the while loop handles it (carry > 0). This creates an extra node for the result list if needed.
  • Empty Stacks in Loop: The pop logic defaults to 0 when stack is empty using conditional expression or check before pop (implemented via ternary).