Skip to main content
CodePeetCodePeet
CodePeet 150

Add Two Numbers

MEDIUMProblemSolveExternal Links

Description

You are given two non-empty linked lists, each representing a non-negative integer. The digits of each number are stored in reverse order, meaning the least significant digit (ones place) comes first, and each node holds exactly one digit (0–9).

Your task is to add the two numbers together and return the result as a new linked list, also in reverse order.

You may assume that neither number has leading zeros, except for the number 0 itself.

In simpler terms: Imagine two numbers written backwards, digit by digit, as chains of nodes. You need to perform addition just like you would on paper — starting from the ones place — and produce a new chain representing the sum.

Examples

Example 1

Input: l1 = [2, 4, 3], l2 = [5, 6, 4]

Output: [7, 0, 8]

Explanation: The list l1 represents the number 342 (digits reversed: 2→4→3). The list l2 represents 465 (digits reversed: 5→6→4). Adding them: 342 + 465 = 807. The result 807 is stored in reverse order as 7→0→8.

Example 2

Input: l1 = [0], l2 = [0]

Output: [0]

Explanation: Both lists represent the number 0. The sum 0 + 0 = 0 is represented as a single node with value 0.

Example 3

Input: l1 = [9, 9, 9, 9, 9, 9, 9], l2 = [9, 9, 9, 9]

Output: [8, 9, 9, 9, 0, 0, 0, 1]

Explanation: l1 represents 9999999 and l2 represents 9999. Their sum is 9999999 + 9999 = 10009998. In reverse order that is 8→9→9→9→0→0→0→1. Notice the result list is longer than both inputs because the addition produced a carry that extended the total number of digits by one.

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

Editorial

Brute Force

Intuition

The most straightforward idea is to convert both linked lists back into actual integers, add them together using normal arithmetic, and then convert the resulting integer back into a linked list in reverse order.

Think of it this way: you receive two chains of digits. You read each chain, reconstruct the original number from those digits, perform the addition you learned in elementary school, and then break the answer back into individual digits for a new chain.

Since the digits are already stored in reverse order (ones place first), reconstructing the number involves multiplying each digit by an increasing power of 10. For example, the list [2, 4, 3] gives us 2×1 + 4×10 + 3×100 = 342.

After adding the two reconstructed numbers, we extract each digit of the sum using modulo 10 and integer division, building the result list one node at a time.

Step-by-Step Explanation

Let's trace through with l1 = [2, 4, 3], l2 = [5, 6, 4]:

Step 1: Initialize multiplier = 1 and num1 = 0. We will build the integer from l1.

Step 2: Read l1 node value 2. num1 = 0 + 2 × 1 = 2. Advance multiplier to 10.

Step 3: Read l1 node value 4. num1 = 2 + 4 × 10 = 42. Advance multiplier to 100.

Step 4: Read l1 node value 3. num1 = 42 + 3 × 100 = 342. l1 is exhausted.

Step 5: Repeat for l2. Reset multiplier = 1, num2 = 0. Process 5→6→4 to get num2 = 5 + 60 + 400 = 465.

Step 6: Compute total = 342 + 465 = 807.

Step 7: Extract digits from total. 807 % 10 = 7, create node(7). total = 807 / 10 = 80.

Step 8: 80 % 10 = 0, create node(0). total = 80 / 10 = 8.

Step 9: 8 % 10 = 8, create node(8). total = 8 / 10 = 0. Done.

Result: Linked list [7, 0, 8].

Brute Force — Convert Lists to Numbers, Add, Convert Back — Watch how we traverse each linked list to reconstruct the integer, perform the addition, and then decompose the result back into a linked list digit by digit.

Algorithm

  1. Traverse l1 from head to tail, accumulating the integer value by multiplying each node's digit by an increasing power of 10 (1, 10, 100, ...)
  2. Repeat the same for l2 to get the second integer
  3. Add the two integers to get the total sum
  4. If the total is 0, return a single node with value 0
  5. While total > 0:
    • Extract the last digit using total % 10
    • Create a new node with that digit and append to the result list
    • Divide total by 10 (integer division)
  6. Return the head of the result linked list

Code

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        // Convert l1 to integer
        long long num1 = 0, multiplier = 1;
        ListNode* curr = l1;
        while (curr) {
            num1 += (long long)curr->val * multiplier;
            multiplier *= 10;
            curr = curr->next;
        }
        
        // Convert l2 to integer
        long long num2 = 0;
        multiplier = 1;
        curr = l2;
        while (curr) {
            num2 += (long long)curr->val * multiplier;
            multiplier *= 10;
            curr = curr->next;
        }
        
        // Add and convert back
        long long total = num1 + num2;
        if (total == 0) return new ListNode(0);
        
        ListNode* dummy = new ListNode(0);
        curr = dummy;
        while (total > 0) {
            curr->next = new ListNode(total % 10);
            curr = curr->next;
            total /= 10;
        }
        
        return dummy->next;
    }
};
class Solution:
    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        # Convert l1 to integer
        num1 = 0
        multiplier = 1
        curr = l1
        while curr:
            num1 += curr.val * multiplier
            multiplier *= 10
            curr = curr.next
        
        # Convert l2 to integer
        num2 = 0
        multiplier = 1
        curr = l2
        while curr:
            num2 += curr.val * multiplier
            multiplier *= 10
            curr = curr.next
        
        # Add and convert back to linked list
        total = num1 + num2
        if total == 0:
            return ListNode(0)
        
        dummy = ListNode(0)
        curr = dummy
        while total > 0:
            curr.next = ListNode(total % 10)
            curr = curr.next
            total //= 10
        
        return dummy.next
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        // Convert l1 to integer
        long num1 = 0, multiplier = 1;
        ListNode curr = l1;
        while (curr != null) {
            num1 += (long) curr.val * multiplier;
            multiplier *= 10;
            curr = curr.next;
        }
        
        // Convert l2 to integer
        long num2 = 0;
        multiplier = 1;
        curr = l2;
        while (curr != null) {
            num2 += (long) curr.val * multiplier;
            multiplier *= 10;
            curr = curr.next;
        }
        
        // Add and convert back
        long total = num1 + num2;
        if (total == 0) return new ListNode(0);
        
        ListNode dummy = new ListNode(0);
        curr = dummy;
        while (total > 0) {
            curr.next = new ListNode((int)(total % 10));
            curr = curr.next;
            total /= 10;
        }
        
        return dummy.next;
    }
}

Complexity Analysis

Time Complexity: O(m + n)

We traverse l1 once (m nodes) to build num1, l2 once (n nodes) to build num2, and then iterate through the digits of the sum (at most max(m, n) + 1 digits). Each step is O(1), so the total time is O(m + n).

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

The result linked list has at most max(m, n) + 1 nodes. We also use O(1) extra variables for num1, num2, and total.

Important limitation: This approach stores the entire number as an integer. For very large numbers (e.g., a 100-digit number), this can cause integer overflow in languages with fixed-size integers like C++ and Java. Python handles arbitrarily large integers natively, but for C++ and Java, this brute force fails when the linked list has more than about 18-19 nodes (exceeding the range of a 64-bit long).

Why This Approach Is Not Efficient

The brute force approach has a critical flaw: integer overflow. Each linked list can have up to 100 nodes, meaning the number can have up to 100 digits. A 100-digit number far exceeds the capacity of any standard integer type:

  • A 64-bit long long in C++ can hold at most about 19 digits (up to ~9.2 × 10^18)
  • A 100-digit number is on the order of 10^99, which is astronomically larger

Even in Python, where integers have arbitrary precision, converting to and from integers is unnecessary work when we can add digit-by-digit directly.

The key insight is that we do not need to reconstruct the full numbers at all. Since the digits are already stored in reverse order (ones place first), we can add them directly — just like how we perform addition by hand on paper, one column at a time, carrying over when the sum exceeds 9. This digit-by-digit simulation avoids any overflow issues and processes each node exactly once.

Comparison showing integer overflow risk with 100-digit numbers versus safe digit-by-digit addition
Comparison showing integer overflow risk with 100-digit numbers versus safe digit-by-digit addition

Optimal Approach - Iterative Digit-by-Digit Simulation

Intuition

Instead of converting to integers, we can add the two numbers digit by digit, exactly like grade-school addition on paper.

Recall how you add two numbers by hand:

  3 4 2
+ 4 6 5
-------

You start from the rightmost column: 2 + 5 = 7 (write 7, carry 0). Next column: 4 + 6 = 10 (write 0, carry 1). Next: 3 + 4 + 1(carry) = 8 (write 8, carry 0). The answer is 807.

The beauty of this problem is that the linked lists already store digits in reverse order — the head node is the ones place. This means we can simply traverse both lists simultaneously from head to tail, adding corresponding digits along with any carry from the previous position.

For each pair of nodes:

  1. Compute the sum = digit from l1 + digit from l2 + carry
  2. The new digit for the result is sum % 10 (the remainder)
  3. The new carry is sum / 10 (either 0 or 1, since the max possible sum is 9 + 9 + 1 = 19)

We continue until both lists are exhausted AND no carry remains. A dummy head node simplifies building the result list — we never need to handle the first node as a special case.

Step-by-Step Explanation

Let's trace through with l1 = [9, 9, 9, 9, 9, 9, 9] and l2 = [9, 9, 9, 9]. This is Example 3, which involves heavy carry propagation and different list lengths.

Step 1: Create a dummy node and set carry = 0. Both pointers start at the heads of l1 and l2.

Step 2: Position 0: l1 digit = 9, l2 digit = 9. Sum = 9 + 9 + 0 = 18. New digit = 18 % 10 = 8. Carry = 18 / 10 = 1. Create node(8).

Step 3: Position 1: l1 digit = 9, l2 digit = 9. Sum = 9 + 9 + 1 = 19. New digit = 19 % 10 = 9. Carry = 19 / 10 = 1. Create node(9).

Step 4: Position 2: l1 digit = 9, l2 digit = 9. Sum = 9 + 9 + 1 = 19. New digit = 9. Carry = 1. Create node(9).

Step 5: Position 3: l1 digit = 9, l2 digit = 9. Sum = 9 + 9 + 1 = 19. New digit = 9. Carry = 1. Create node(9). l2 is now exhausted.

Step 6: Position 4: l1 digit = 9, l2 digit = 0 (exhausted). Sum = 9 + 0 + 1 = 10. New digit = 0. Carry = 1. Create node(0).

Step 7: Position 5: l1 digit = 9, l2 digit = 0. Sum = 9 + 0 + 1 = 10. New digit = 0. Carry = 1. Create node(0).

Step 8: Position 6: l1 digit = 9, l2 digit = 0. Sum = 9 + 0 + 1 = 10. New digit = 0. Carry = 1. Create node(0). l1 is now exhausted.

Step 9: Both lists exhausted but carry = 1. Sum = 0 + 0 + 1 = 1. Create node(1). Carry = 0.

Result: [8, 9, 9, 9, 0, 0, 0, 1], representing 10009998.

Iterative Digit-by-Digit Addition with Carry Propagation — Watch how two linked lists of different lengths are added digit by digit. When one list ends, we treat missing digits as 0. The carry propagates through positions until both lists are exhausted and no carry remains.

Algorithm

  1. Create a dummy head node for the result list and set a pointer curr to it
  2. Initialize carry = 0
  3. While l1 is not null, OR l2 is not null, OR carry is non-zero:
    • Read digit1 = l1.val if l1 exists, else 0
    • Read digit2 = l2.val if l2 exists, else 0
    • Compute sum = digit1 + digit2 + carry
    • New digit = sum % 10
    • New carry = sum / 10
    • Create a new node with the new digit and attach it to curr.next
    • Advance curr to curr.next
    • Advance l1 to l1.next if l1 exists
    • Advance l2 to l2.next if l2 exists
  4. Return dummy.next (the real head of the result list)

Code

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode* dummy = new ListNode(0);
        ListNode* curr = dummy;
        int carry = 0;
        
        while (l1 || l2 || carry) {
            int digit1 = l1 ? l1->val : 0;
            int digit2 = l2 ? l2->val : 0;
            
            int sum = digit1 + digit2 + carry;
            carry = sum / 10;
            int newDigit = sum % 10;
            
            curr->next = new ListNode(newDigit);
            curr = curr->next;
            
            if (l1) l1 = l1->next;
            if (l2) l2 = l2->next;
        }
        
        return dummy->next;
    }
};
class Solution:
    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        dummy = ListNode(0)
        curr = dummy
        carry = 0
        
        while l1 or l2 or carry:
            digit1 = l1.val if l1 else 0
            digit2 = l2.val if l2 else 0
            
            total = digit1 + digit2 + carry
            carry = total // 10
            new_digit = total % 10
            
            curr.next = ListNode(new_digit)
            curr = curr.next
            
            l1 = l1.next if l1 else None
            l2 = l2.next if l2 else None
        
        return dummy.next
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0);
        ListNode curr = dummy;
        int carry = 0;
        
        while (l1 != null || l2 != null || carry != 0) {
            int digit1 = (l1 != null) ? l1.val : 0;
            int digit2 = (l2 != null) ? l2.val : 0;
            
            int sum = digit1 + digit2 + carry;
            carry = sum / 10;
            int newDigit = sum % 10;
            
            curr.next = new ListNode(newDigit);
            curr = curr.next;
            
            if (l1 != null) l1 = l1.next;
            if (l2 != null) l2 = l2.next;
        }
        
        return dummy.next;
    }
}

Complexity Analysis

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

We traverse both linked lists in a single pass. The loop runs for max(m, n) iterations (plus at most 1 extra iteration for a final carry). At each iteration, we do O(1) work: reading digits, computing the sum, creating a node. Therefore the total time is O(max(m, n)).

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

The result linked list contains at most max(m, n) + 1 nodes (the extra node appears when there is a final carry). If we do not count the output as extra space (since it is required by the problem), the auxiliary space is O(1) — we only use a few integer variables (carry, digit1, digit2, sum) and pointers.

This is the optimal solution: we cannot do better than O(max(m, n)) time since we must read every digit of both inputs at least once, and we need O(max(m, n)) space for the output.