2. Add Two Numbers
Model: qwen3.5:9b
Topics: Linked List,Math,Recursion
FAANG asked: 1
Acceptance rate: 35.7%
Problem Breakdown
We are given two non-empty linked lists where each node contains a single digit of a number, stored in reverse order (least significant digit at the head). We need to add these numbers and return their sum as another linked list following the same format.
Inputs: Two ListNode objects (l1, l2).
Outputs: A new ListNode representing the sum.
Constraints & Edge Cases:
- Different Lengths: One list might be longer than the other; we must handle missing nodes by treating them as 0.
- Carry Over: If a column sums to , we carry to the next node. This can propagate all the way through or create an extra head node (e.g.,
9+1). - Non-Empty Guarantee: Constraints state lists are non-empty, so no null checks for empty inputs needed initially.
- Value Range: Digits 0-9; standard integer overflow isn’t a concern in Python, but logic must handle the carry manually regardless of language limits (e.g., C++
intvslong long).
Intuition
A brute-force approach would be to convert both linked lists into integers, add them using arithmetic operators, and then construct a new list from the result. While this works for small numbers, it fails in two ways:
- Overflow: In languages like C++ or Java, standard integer types cannot hold values with more than ~18-20 digits (though Python handles arbitrary precision). The problem implies we should treat these as linked lists of potentially large sizes (), making conversion inefficient if not done carefully.
- Memory: Converting to a number requires storing the whole value, whereas addition can be performed digit-by-digit without materializing the full integer first.
The key insight is that we are essentially simulating manual column-wise addition on paper. We start at the heads of both lists (the ones place), add them along with any carry from the previous position, store sum % 10 in a new node, and pass sum // 10 as the carry to the next iteration. This process continues until we exhaust all nodes in both lists AND there is no remaining carry.
Approach
I will use an iterative approach with a dummy head node for simplicity:
- Initialize three pointers: one for each input list (
l1,l2) and one for the result list (curr). I’ll create adummynode to serve as the placeholder for the start of our new list, so we don’t have to handle null checks on the head separately. - Initialize
carry = 0. - Loop while either input pointer is valid OR there is an active carry:
- Get values from current nodes in
l1andl2, defaulting to 0 if a list has been exhausted. - Calculate total sum (
val1 + val2 + carry). - Create new node with value
sum % 10. Link it after the dummy’s previous position. - Update pointers: move
l1,l2forward if they exist; update result pointer to next created node. - Update
carry = sum // 10.
- Get values from current nodes in
- Return
dummy.nextas the actual head of our new list.
Complexity Analysis
- Time Complexity: , where and are lengths of
l1andl2. We iterate through each node at most once per list plus potentially one extra iteration for a final carry. - Space Complexity: auxiliary space if we exclude the output linked list (which is required). If including the result, it’s proportional to .
Solution
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def addTwoNumbers(l1: ListNode, l2: ListNode) -> ListNode:
dummy = ListNode(0) # Dummy head to simplify list construction logic
curr = dummy # Pointer for the result list tail
carry = 0
while l1 or l2 or carry:
val1 = l1.val if l1 else 0
val2 = l2.val if l2 else 0
total = val1 + val2 + carry
curr.next = ListNode(total % 10) # Create new node with digit sum
curr = curr.next # Move result pointer forward
carry = total // 10 # Calculate next carry bit
if l1: l1 = l1.next # Advance input pointers only if valid
if l2: l2 = l2.next
return dummy.next # Return actual head of the new list
Edge Cases Handled
- Different Lengths: The condition
while l1 or l2ensures we continue processing as long as one list has remaining digits, treating missing nodes implicitly as 0. - Final Carry: If a carry remains after both lists are exhausted (e.g., adding two numbers ending in 9), the loop continues for that final iteration to create an extra node at the end of the result list.
- Single Node Lists: The logic holds naturally;
l1orl2becomes None immediately, and values default to 0 correctly.