LeetCode #2: Add Two Numbers

Adding two numbers represented as linked lists, digit by digit, with carry.

Difficulty: MediumCategory: Linked List, MathTime: 6 min read

The 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.

💡 Note: The numbers don't have leading zeros, except for the number 0 itself.

Example

Input: L1 = [2,4,3], L2 = [5,6,4]
Output: [7,0,8]
Explanation: 342 + 465 = 807

How Carry Works

Since each node holds a single digit (0–9), when we add two digits and the sum is 10 or more, we carry over the extra to the next digit.

Rule:

Sum = digit1 + digit2 + carry
Current digit = sum % 10
New carry = Math.floor(sum / 10)

What is a Linked List?

A linked list is a linear data structure where each element (called a node) contains a value and a reference (or "pointer") to the next node in the sequence.

Structure of a Node

Each node has two parts:

val: The data (in this problem, a single digit)
next: A pointer to the next node (or null if it's the last)

class ListNode {
    val: number;
    next: ListNode | null;

    constructor(val: number = 0, next: ListNode | null = null) {
        this.val = val;
        this.next = next;
    }
}

Visual Example: [2 → 4 → 3]

This represents the number 342 because digits are stored in reverse order.

null

Why reverse order? It allows us to process digits from least significant to most — just like how we add numbers on paper, starting from the right most digit.

When Are Linked Lists Used?

When you need efficient insertions/deletions at the start or middle
To implement stacks, queues, or hash tables
In memory-constrained systems where dynamic allocation is preferred over large arrays
As a building block for more complex structures (trees, graphs)

The Algorithm

Create a dummy head to simplify result list creation
Traverse both lists simultaneously
Add digits + carry at each step
Create new node with the digit (sum % 10)
Update carry for next iteration
Continue until both lists and carry are exhausted

Solution (JavaScript)

function ListNode(val, next) {
  this.val = (val === undefined ? 0 : val);
  this.next = (next === undefined ? null : next);
}

function addTwoNumbers(l1, l2) {
  const dummy = new ListNode(0);
  let current = dummy;
  let carry = 0;

  while (l1 || l2 || carry) {
    const val1 = l1 ? l1.val : 0;
    const val2 = l2 ? l2.val : 0;
    
    const sum = val1 + val2 + carry;
    carry = Math.floor(sum / 10);
    const digit = sum % 10;

    current.next = new ListNode(digit);
    current = current.next;

    if (l1) l1 = l1.next;
    if (l2) l2 = l2.next;
  }

  return dummy.next;
}

Complexity

Time: O(max(m, n)) — where m and n are lengths of the lists
Space: O(max(m, n)) — for the output list

Visualizer

Step-by-Step: 342 + 465 = 807

Click 'Play' to watch how carry propagates through digits.

Input:

Carry:

Output (so far):

No digits yet...

Step 1 of 4 • Running...

Summary

This problem combines linked list traversal with elementary math. The key is handling the carry correctly and continuing the loop even after one list ends.

It‘s a common interview question because it tests attention to edge cases and clean pointer manipulation.

Real-World Applications

At first glance, "Add Two Numbers" might seem like just another coding puzzle, but it’s actually a simplified version of a critical concept used across computer science.

Big Integers & Cryptography

Numbers in most programming languages have limits. But encryption (like RSA) uses 2048-bit or 4096-bit primes far too large for standard types. Systems represent these as digit arrays and use digit-by-digit addition, just like in this problem.

💰 Financial Calculations

Banks avoid floating-point math
(0.1 + 0.2 !== 0.3)
by storing values as integers (e.g., cents). Adding large amounts requires carry-aware arithmetic exactly what this problem teaches.

🛠️ Programming Languages

Languages like Python and Java support arbitrarily large integers (BigInteger). These are built using linked structures or arrays and processed digit-by-digit — the same logic you’re implementing here.

Algorithmic Thinking

This problem teaches carry management, pointer traversal, and edge case handling skills used in parsing, state machines, and even game development.

Fun Fact: The largest known prime has over 24 million digits. You can‘t store that in an int — it‘s stored and added using logic just like this!

View All Challenges