Add Two Numbers

Difficulty: Medium

Problem

Two non-negative integers are each stored as a linked list, one digit per node, with the least significant digit first. Add the two numbers and return the total as a linked list in that same reversed layout.

Both lists have at least one node, and neither number has extra leading zeros (the number 0 itself is a single node).

Example

Input: l1 = [8,7,5], l2 = [5,6]
Output: [3,4,6]
Explanation: 578 + 65 = 643, and 643 stored with the ones digit first is [3,4,6]. Carries move forward along the lists: 8+5=13 writes 3 and carries 1, then 7+6+1=14 writes 4 and carries 1, then 5+1=6.

Brute-force approach, Convert to Integers, Add, Convert Back

Convert both linked lists to integers, add them, then convert the sum back to a linked list. Note: this can overflow for very large numbers.

Steps

  1. Traverse l1, build the number (reverse digit order)
  2. Traverse l2, build the number
  3. Add the two numbers
  4. Convert the sum to a linked list in reverse order
  5. Return the result

Time complexity: O(n + m) · Space complexity: O(max(n, m))

Trade-offs

  • Integer overflow for numbers with many digits
  • Extra conversion steps add complexity

Optimal approach, Elementary Math: Add Digit by Digit

Key insight: Process digits left-to-right with a carry variable, just like elementary addition from right to left.

Process both lists simultaneously, adding corresponding digits along with any carry. Create a new node for each digit of the result. This handles any length naturally without overflow risk.

Steps

  1. Create a dummy node and carry = 0
  2. While either list has nodes or carry > 0:
  3. sum = (l1.val or 0) + (l2.val or 0) + carry
  4. Create node with sum % 10, update carry = sum / 10
  5. Return dummy.next

Time complexity: O(max(n, m)) · Space complexity: O(max(n, m))

Pseudocode

function addTwoNumbers(l1, l2):
    dummy = ListNode(0)
    current = dummy
    carry = 0
    while l1 OR l2 OR carry:
        sum = carry
        if l1: sum += l1.val; l1 = l1.next
        if l2: sum += l2.val; l2 = l2.next
        carry = sum / 10
        current.next = ListNode(sum % 10)
        current = current.next
    return dummy.next

Hints

  • Process both lists digit by digit from head to tail
  • Keep track of the carry from each addition
  • Don't forget to handle the final carry

Complexity questions

What is the time complexity of converting to numbers and back?

O(n + m). We traverse both lists once O(n+m) and convert the sum back O(max(n,m)), giving O(n+m).

What is the main problem with the brute force approach?

Integer overflow for very large numbers. If the linked lists represent numbers with hundreds of digits, they won't fit in a standard integer type, causing overflow.

What is the time complexity of the digit-by-digit approach?

O(max(n,m)). We process each digit once, iterating max(n,m) + 1 times (extra for possible carry).

What is the space complexity of the optimal approach?

O(max(n,m)). The result list has at most max(n,m) + 1 nodes.

Check your understanding of Add Two Numbers

Why are digits stored in reverse order?

Because the head represents the least significant digit, making addition natural left to right. Storing digits in reverse means we process from least significant to most significant, just like hand addition from right to left. The head is the ones place.

When does a carry occur?

When the sum of two digits (plus carry) is >= 10. If the sum of digits at any position plus the incoming carry is 10 or more, we keep sum % 10 as the digit and carry over sum / 10 to the next position.

What is the result of adding [9,9] (representing 99) and [1] (representing 1)?

[0,0,1] (representing 100). 99 + 1 = 100. In reverse-order linked list form, 100 is stored as [0,0,1]. Note the result has more digits than either input.

Related problems

Keep practising