150NeetCode 150

40.Add Two Numbers

MediumLinked List · 6/11
LeetCode #2Video

Problem

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order (the head is the ones digit), and each node holds a single digit.

Add the two numbers and return the sum as a linked list in the same reverse-digit format. The numbers have no leading zeros, except the number 0 itself.

Examples

Input:  l1 = [2, 4, 3], l2 = [5, 6, 4]
Output: [7, 0, 8]
Explanation: 342 + 465 = 807.
Input:  l1 = [0], l2 = [0]
Output: [0]
Input:  l1 = [9, 9, 9, 9, 9, 9, 9], l2 = [9, 9, 9, 9]
Output: [8, 9, 9, 9, 0, 0, 0, 1]
Explanation: 9999999 + 9999 = 10009998; the final carry creates a new node.

Constraints

  • The number of nodes in each linked list is in the range [1, 100].
  • 0 <= Node.val <= 9
  • The lists represent numbers without leading zeros.

💡 Key Insight

Reverse order is a gift: the heads are the least significant digits, which is exactly where grade-school addition starts. Walk both lists together, add the two digits plus carry, write sum % 10 into a new node and carry sum / 10 forward. Up to 100 digits means the numbers do not fit in long, so converting to primitives is not an option.

Brute Force (BigInteger Conversion)

TimeO(max(m, n)) digit work (BigInteger addition is linear in the number of digits).SpaceO(max(m, n))

Intuition

Turn each list into an actual number, add them, and turn the result back into a list. Because a 100-digit number overflows long, we must use BigInteger.

Algorithm

  1. Build the digit string of each list by prepending digits (reversing the order).
  2. Parse both strings as BigInteger and add them.
  3. Walk the sum's string from the last character to the first, appending a node for each digit.

Visualization

l1 = 2 -> 4 -> 3   => "342"
l2 = 5 -> 6 -> 4   => "465"
342 + 465 = 807    => digits read right-to-left: 7 -> 0 -> 8

Code

java
import java.math.BigInteger;

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        BigInteger sum = toNumber(l1).add(toNumber(l2));
        String digits = sum.toString();
        ListNode dummy = new ListNode(0);
        ListNode tail = dummy;
        for (int i = digits.length() - 1; i >= 0; i--) {
            tail.next = new ListNode(digits.charAt(i) - '0'); // least significant first
            tail = tail.next;
        }
        return dummy.next;
    }

    private BigInteger toNumber(ListNode node) {
        StringBuilder sb = new StringBuilder();
        for (; node != null; node = node.next) {
            sb.append(node.val);
        }
        return new BigInteger(sb.reverse().toString()); // head is the ones digit
    }
}

Complexity

  • Time: O(max(m, n)) digit work (BigInteger addition is linear in the number of digits).
  • Space: O(max(m, n)) — strings and BigInteger objects.

Complexity Comparison

Approach Time Space (extra)
BigInteger Conversion O(max(m,n)) O(max(m,n))
Recursion O(max(m,n)) O(max(m,n))
Iterative with Carry O(max(m,n)) O(1)

Common Pitfalls

  • Converting to int/long — 100-digit numbers overflow immediately.
  • Forgetting the final carry: [5] + [5] must return [0, 1], not [0].
  • Stopping when the shorter list ends instead of continuing with the longer one.
  • Reversing the lists first — unnecessary, since reverse order already starts at the ones digit.
  • Dereferencing l1.val without a null check once one list is exhausted.