DSA Explained
#2

Add Two Numbers

Medium
LeetCode

You are given two linked lists representing two non-negative integers. The digits are stored in reverse order, meaning the first node is the ones digit. Add the two numbers and return the sum as a new linked list.

💡 In plain English

Remember doing addition with paper and pencil in school? You lined up numbers by their ones, tens, and hundreds columns, added each column from right to left, and carried over a 1 whenever the sum reached 10 or more. Because the linked lists are already in reverse order, you can add them column by column just like grade-school math!

Reference: LeetCode #2 • Add Two Numbers

Approach
Execution Timeline (Optimal (Simulation))Click any step to inspect state & code

Linked List Addition Engine

Optimal: Elementary Math Simulation (With Carry)
Step 3 / 5
3

Column 2 (Tens): 4 + 6 = 10 (Carry 1!)

TRAVERSING

Add the tens digits: 4 + 6 + 0 (carry) = 10. Since 10 is 10 or greater, write down 0 and carry over 1 to the next column!

List 1 (l1): Represents 342Reverse Order
2
[0]
→
4
↓ p1
→
3
[2]
→null
List 2 (l2): Represents 465Reverse Order
5
[0]
→
6
↓ p2
→
4
[2]
→null
Result List (dummy.next): Represents 8072 nodes created
dummy(0)
→
7
[0]
→
0
curr
Elementary Column Math
Column Formula: v1 + v2 + carry_in
Calculation: 4 + 6 + 0 = 10
New Node: 0New Carry: 1
State Variables
v1 (l1)4
v2 (l2)6
carry1
Sum = 10. Node gets 0, carry 1 passed to next column.
1
function addTwoNumbers(l1, l2) {
2
const dummy = new ListNode(0);
3
let curr = dummy;
4
let carry = 0;
5
while (l1 !== null || l2 !== null || carry !== 0) {
6
const v1 = l1 !== null ? l1.val : 0;
7
const v2 = l2 !== null ? l2.val : 0;
8
const sum = v1 + v2 + carry;
9
carry = Math.floor(sum / 10);
10
curr.next = new ListNode(sum % 10);
11
curr = curr.next;
12
if (l1 !== null) l1 = l1.next;
13
if (l2 !== null) l2 = l2.next;
14
}
15
return dummy.next;
16
}
Optimal (Simulation) • Synchronized Line TraceLine 9 of 16
→ Executing Statement:Sum is 10: node gets 0 (10 % 10), carry becomes 1.

Why is Column Math the Best Solution?

Why converting to normal numbers crashes, and why elementary math works on numbers of any size.

Step-by-Step Logic
01. First Idea

Convert to Number

Read both lists into normal numbers, calculate 342 + 465 = 807, and turn 807 into a list.

Trap: Seems easy at first
02. The Crash

Numbers Get Too Big!

Numbers can have 100 digits! Standard computer variables break after 18 digits. Trying to hold 100 digits crashes.

Limit: 100 digits exceeds memory
03. The Secret

Reversed Order is a Gift

Notice: The list starts at the ones digit! This is exactly how we write numbers when adding by hand on paper.

Insight: Start from the ones digit
04. Paper Math

Add Column by Column

Sum = digit1 + digit2 + carry. New digit is sum % 10. Next carry is sum / 10.

Work: Instant math per column
05. Optimal

Build in One Pass

Create answer nodes as you step forward. Fast O(n) time, minimal memory, and zero risk of numbers overflowing!

Result: Fast, safe & simple
Active Selection Details

Optimal: Elementary Math Simulation (With Carry)

Time: O(max(m, n)) — FastAux Space: O(1) — Uses almost no memory
Time Complexity: O(max(m, n)) — Fast
Best:O(max(m, n))
Average:O(max(m, n))
Worst:O(max(m, n))

We step through both lists together once. Adding two single digits takes only 1 instant step.

Space Complexity: O(1) — Uses almost no memory
Auxiliary Memory: O(1)

We only use a couple of simple variables (like carry and sum). We do not store extra lists in memory.

Example Test Cases

Simple examples
Example 1 (Standard Addition)
Input: l1 = [2, 4, 3], l2 = [5, 6, 4]
Output: [7, 0, 8]
This represents 342 + 465 = 807. In reverse, 807 is [7, 0, 8].
Example 2 (Adding Zeros)
Input: l1 = [0], l2 = [0]
Output: [0]
0 + 0 = 0.
Example 3 (Carrying Over at the End)
Input: l1 = [9, 9, 9], l2 = [1]
Output: [0, 0, 0, 1]
999 + 1 = 1000. Notice the extra 1 node created at the very end!

Rules & Limits

Constraints
  • Up to 100 digits

    The number of nodes in each linked list is in the range [1, 100] (exceeds 64-bit integer limits).

  • Single digits (0 to 9)

    Each node stores a single digit 0 ≤ Node.val ≤ 9.

  • No leading zeros

    Numbers will never start with 0, except for the number 0 itself.

  • Reversed order

    The first node is the ones digit, making column math easy to start right away.

Important Things to Remember

Key Lessons
1. The Fake Starting Node

Creating a linked list from scratch is messy because you don't have a first node yet. Making a fake starting node (dummy = ListNode(0)) keeps your code simple. When done, just return dummy.next!

2. Keep Going Until Everything Is Done

Use while (l1 || l2 || carry). This loop keeps running if one list is longer than the other, or if there is a leftover carry 1 at the very end.

3. Add Column by Column

Don't turn the list into a normal number first. 100-digit numbers crash normal variables. Adding node-by-node is simple, works for numbers of any size, and uses very little memory.

Related Problems & Linked List Practice: Explore All 12 Patterns →
#1 Two Sum (Easy) #3 Longest Substring Without Repeating Characters (Medium) #206 Reverse Linked List (Easy) #445 Add Two Numbers II (Forward Order) (Medium) #43 Multiply Strings (Medium) #67 Add Binary (Easy)