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
l1orl2.
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
- Stack Initialization: Traverse both input lists
l1andl2. 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. - 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
carryassum // 10.
- 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
headpointer updates. I will use a standard “dummy” approach where nodes are appended to a tail, then reversed? No, simpler: Use anew_headvariable 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 noden = 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
resultlist (updatehead = 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
dummynode to simplify logic or just trackhead. Trackingheadand updating pointers (new_node.next = current_head; current_head = new_node) works perfectly in O(1).
Complexity Analysis
- Time: , 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: . 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 stack2ensures 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
poplogic defaults to 0 when stack is empty using conditional expression or check before pop (implemented via ternary).