Domain 2MediumCORE

Add Two Numbers

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.

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

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 ≥10\geq 10, we carry 11 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++ int vs long 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:

  1. 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 (N=100N=100), making conversion inefficient if not done carefully.
  2. 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:

  1. Initialize three pointers: one for each input list (l1, l2) and one for the result list (curr). I’ll create a dummy node 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.
  2. Initialize carry = 0.
  3. Loop while either input pointer is valid OR there is an active carry:
    • Get values from current nodes in l1 and l2, 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, l2 forward if they exist; update result pointer to next created node.
    • Update carry = sum // 10.
  4. Return dummy.next as the actual head of our new list.

Complexity Analysis

  • Time Complexity: O(max⁡(N,M))O(\max(N, M)), where NN and MM are lengths of l1 and l2. We iterate through each node at most once per list plus potentially one extra iteration for a final carry.
  • Space Complexity: O(1)O(1) auxiliary space if we exclude the output linked list (which is required). If including the result, it’s proportional to max⁡(N,M)\max(N, M).

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 l2 ensures 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; l1 or l2 becomes None immediately, and values default to 0 correctly.