Add Two Numbers

Difficulty: Medium

Problem

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each node contains a single digit. Add the two numbers and return the sum as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Example

Input: l1 = [2,4,3], l2 = [5,6,4]
Output: [7,0,8]
Explanation: 342 + 465 = 807. Stored in reverse: [7,0,8].

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))