Linked List · LC #2
Add Two Numbers
Add two non-negative integers stored as reversed linked lists digit-by-digit with carry propagation. Returns the sum as a reversed linked list.
Statement
Problem & Approach
Problem statement, sample I/O, and key reasoning.
You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each of their nodes 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.
Sample I/O
Input: l1 = [2,4,3], l2 = [5,6,4] (342 + 465 = 807) Output: [7,0,8] Input: l1 = [9,9,9,9], l2 = [9,9,9] Output: [8,9,9,0,1] (9999 + 999 = 10998)
Intuition
How to Think About It
Intuition
Because digits are already in reverse order (least significant digit first), we can simulate elementary school addition from left to right - the same direction we traverse the list. At each position we sum two digits plus any carry from the previous position, emit digit = sum % 10, and propagate carry = sum / 10. The reverse storage makes this perfectly aligned.
Core Concept
Use a dummy head and a curr pointer. Loop while l1, l2, or carry is non-zero. At each step: sum = carry + (l1.val if l1 else 0) + (l2.val if l2 else 0). New node value = sum % 10; carry = sum / 10. Advance l1 and l2 if non-null. The carry check in the loop condition handles the final overflow digit (e.g. 999+1 → 1000). Time: O(max(m,n)), Space: O(max(m,n)).
When to use
Any digit-by-digit arithmetic on linked-list representations of numbers; also when numbers are too large to fit in a standard integer.
When NOT to use
When digits are stored in normal (most-significant first) order - requires reversal first or a stack-based approach (LC #445). When numbers fit in standard integer types - just convert and add.
Key Insights
What to Know Cold
- Reverse storage means digits are already aligned for left-to-right addition - no reversal needed.
- The loop condition `while (l1 || l2 || carry)` handles lists of different lengths AND the final carry in one clause.
- Dummy head node removes special handling for the first result node.
- Edge: if one list is longer, treat missing digits as 0 - the null check handles this.
- Final carry digit: if sum overflows (e.g. 99+1=100) the while-loop creates the extra node via the `carry != 0` condition.
1 example
Worked Examples
Different-length lists with final carry
[9,9,9,9] + [9,9,9] = 9999+999 = 10998 → [8,9,9,0,1]
Carry arithmetic with dummy head
function addTwoNumbers(l1: ListNode | null, l2: ListNode | null): ListNode | null {
const dummy = new ListNode(0);
let curr = dummy, carry = 0;
while (l1 || l2 || carry) {
let s = carry;
if (l1) { s += l1.val; l1 = l1.next; }
if (l2) { s += l2.val; l2 = l2.next; }
carry = Math.floor(s / 10);
curr.next = new ListNode(s % 10);
curr = curr.next!;
}
return dummy.next;
}Output: [8,9,9,0,1]
Demonstrates carry propagation across lists of unequal length with overflow - the hardest edge case interviewers check.