Love, Order, Progress

00

Problem Statement

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.

Example 1

l1: [2, 4, 3]

l2: [5, 6, 4]

Output: [7, 0, 8]

Reverse representations correspond to:
342 + 465 = 807.

Example 2

l1: [0]

l2: [0]

Output: [0]

Single zero identity:
0 + 0 = 0.

Example 3

l1: [9,9,9,9,9,9,9]

l2: [9,9,9,9]

Output: [8,9,9,9,0,0,0,1]

Ripple carry expands length:
9999999 + 9999 = 10009998.

Constraints & Invariants

The number of nodes in each linked list is in the range $[1, 100]$ .
$0 \le \text{Node.val} \le 9$ for all nodes.
Guaranteed that the list represents a number that does not have leading zeros (except the number 0 itself).

Critical Observation: Since each list can contain up to

100

nodes, the represented integers can reach magnitude

10^{100} - 1

. This exceeds 64-bit integer capacity (

2^{64}-1 \approx 1.84 \times 10^{19}

) by over 80 orders of magnitude! Converting to native integers will inevitably cause integer overflow.

The canonical LeetCode C++ signature:

C++

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        
    }
};

01

Mathematical Representation · Little-Endian Positional Numeral System

In standard radix- $b$ notation (where $b = 10$ ), a non-negative integer is represented as a polynomial evaluated at base $b$ . Because the singly linked list stores the digits in reverse order, the head node contains the least significant digit (LSD, corresponding to $10^0$ ), and each subsequent pointer step increment corresponds to the next ascending power of 10.

Algebraic DefinitionPositional Digit Stream & Value Mapping

Let a singly-linked list of length $m$ be modeled as an ordered tuple of digits:

L_1 = (a_0, a_1, \dots, a_{m-1}) \in \{0, 1, \dots, 9\}^m, \quad L_2 = (b_0, b_1, \dots, b_{n-1}) \in \{0, 1, \dots, 9\}^n

The bijective numerical evaluation function $V : \bigcup_{k \ge 1} \{0, \dots, 9\}^k \to \mathbb{N}_0$ is:

V(L_1) = \sum_{k=0}^{m-1} a_k \cdot 10^k, \qquad V(L_2) = \sum_{k=0}^{n-1} b_k \cdot 10^k

Target: Construct a new sequence

L_S = (s_0, s_1, \dots, s_{K-1})

such that:

V(L_S) = V(L_1) + V(L_2) = \sum_{k=0}^{m-1} a_k 10^k + \sum_{k=0}^{n-1} b_k 10^k = \sum_{k=0}^{K-1} s_k 10^k

where

s_k \in \{0, 1, \dots, 9\}

and

K \in \{\max(m, n), \max(m, n) + 1\}

.

Visual · Positional Rank Correspondence (Example 1: 342 + 465 = 807)

List l1: [2 → 4 → 3] corresponds to 342

k = 0 (10⁰)

2

→

k = 1 (10¹)

4

→

k = 2 (10²)

3

→ nullptr

List l2: [5 → 6 → 4] corresponds to 465

k = 0 (10⁰)

5

→

k = 1 (10¹)

6

→

k = 2 (10²)

4

→ nullptr

Output Sum List: [7 → 0 → 8] corresponds to 807

k = 0 (10⁰)

7

→

k = 1 (10¹)

0

→

k = 2 (10²)

8

→ nullptr

The reverse orientation is an immense computational gift: in elementary addition, human arithmetic and digital ALUs proceed from least significant digit to most significant digit because the carry propagates strictly from rank $k$ to rank $k+1$ . Hence, the singly linked list can be processed in a single forward pass without needing stack reversal or double-ended queues!

C++

// Anti-Pattern: Attempting to reconstruct native 64-bit integers
// Fails when list length m, n > 19 digits (max uint64_t ≈ 1.84 * 10^19)
class SolutionNaiveOverflow {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        unsigned long long num1 = 0, num2 = 0;
        unsigned long long base = 1;

        // Traverse and multiply by 10^k
        while (l1) {
            num1 += l1->val * base; // OVERFLOW when length > 19 (n can be 100!)
            base *= 10;
            l1 = l1->next;
        }

        // Direct arithmetic evaluation in CPU registers is impossible for 100 digits!
        // We must stream and process digit-by-digit like an arbitrary-precision ALU.
        return nullptr;
    }
};

02

Formal Carry Recurrence & Invariant Proof

To handle arbitrary lengths without allocating variable-length buffers or bignum objects, we formalize the addition as a deterministic finite-state transducer acting on the discrete sequence index $k \ge 0$ .

Theorem & RecurrenceColumn Addition & Carry State Invariant

Let the input sequences be zero-extended for all indices $k \ge 0$ :

\tilde{a}_k = \begin{cases} a_k & \text{if } 0 \le k < m \\ 0 & \text{if } k \ge m \end{cases}, \qquad \tilde{b}_k = \begin{cases} b_k & \text{if } 0 \le k < n \\ 0 & \text{if } k \ge n \end{cases}

Define the carry sequence $(c_k)_{k=0}^{\infty}$ and digit sequence $(s_k)_{k=0}^{\infty}$ inductively:

c_0 = 0

\sigma_k = \tilde{a}_k + \tilde{b}_k + c_k \quad (\text{intermediate column sum})

s_k = \sigma_k \bmod 10 \quad (s_k \in \{0, 1, \dots, 9\})

c_{k+1} = \left\lfloor \frac{\sigma_k}{10} \right\rfloor

Invariant Proof: Carry Boundedness

Claim: $c_k \in \{0, 1\}$ for all $k \ge 0$ .

Proof by Induction: Base case: $c_0 = 0 \in \{0, 1\}$ . Assume induction hypothesis $c_k \in \{0, 1\}$ . Since $\tilde{a}_k \le 9$ and $\tilde{b}_k \le 9$ :

\sigma_k = \tilde{a}_k + \tilde{b}_k + c_k \le 9 + 9 + 1 = 19

Applying the floor function gives:

c_{k+1} = \left\lfloor \frac{\sigma_k}{10} \right\rfloor \le \left\lfloor \frac{19}{10} \right\rfloor = 1

Since $\sigma_k \ge 0$ , $c_{k+1} \ge 0$ . Therefore $c_{k+1} \in \{0, 1\}$ for all $k \ge 0$ . Q.E.D.

Halting Criterion: The process halts at the minimal rank

K

where

k \ge \max(m, n)

and

c_k = 0

. Hence the length of the result list satisfies

\max(m, n) \le K \le \max(m, n) + 1

.

ARCHITECTURE SCHEMA

Rendering diagram...

03

Execution State Trace · Cascading Ripple Carry

The most demanding structural edge case occurs when the input lengths are asymmetric and a continuous series of nines creates a long carry chain that propagates beyond the original length of both lists (Example 3).

Trace Table · l1 = [9,9,9,9,9,9,9] (m = 7), l2 = [9,9,9,9] (n = 4)

Rank k	a_k (l1)	b_k (l2)	c_k (in)	σ_k = a_k + b_k + c_k	s_k = σ_k % 10	c_{k+1} (out)	Appended Node
k = 0	9	9	0	9 + 9 + 0 = 18	8	1	Node(8)
k = 1	9	9	1	9 + 9 + 1 = 19	9	1	Node(9)
k = 2	9	9	1	9 + 9 + 1 = 19	9	1	Node(9)
k = 3	9	9	1	9 + 9 + 1 = 19	9	1	Node(9)
k = 4	9	0 (null)	1	9 + 0 + 1 = 10	0	1	Node(0)
k = 5	9	0 (null)	1	9 + 0 + 1 = 10	0	1	Node(0)
k = 6	9	0 (null)	1	9 + 0 + 1 = 10	0	1	Node(0)
k = 7	0 (null)	0 (null)	1	0 + 0 + 1 = 1	1	0	Node(1)

Final Chain: [8, 9, 9, 9, 0, 0, 0, 1] →

10{,}009{,}998

. Length expanded from

m=7

to

K = m + 1 = 8

nodes.

04

Sentinel (Dummy Head) Pattern & Memory Semantics

When constructing a dynamically allocated linked list, a common implementation source of bugs is distinguishing the initialization of the list head from the subsequent append operations:

IdiomThe Dummy Head (Sentinel) Invariant

Without a dummy node, every iteration requires a conditional branch:

if (head == nullptr) { head = tail = new ListNode(val); } else { tail->next = new ListNode(val); tail = tail->next; }

By allocating a local stack object ListNode dummy(0);:

No heap allocation for the dummy: zero heap fragmentation and automatic destructor reclamation.
Uniform loop body: tail->next = new ListNode(...) unconditionally executes every iteration.
The true head is cleanly accessed via dummy.next.

05

Optimal C++ Implementations

Approach 1 · Iterative with Sentinel Pointer (Production Standard)

Single-pass iterative loop over the union predicate l1 != nullptr || l2 != nullptr || carry != 0. Guarantees zero heap leak of dummy node and minimal CPU instruction footprint:

C++

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        // Sentinel node: eliminates branch checks for the head of the new list
        ListNode dummy(0);
        ListNode* tail = &dummy;

        int carry = 0; // Invariant: carry in {0, 1}

        // Loop invariant: continue while digits remain in l1 or l2,
        // or a pending carry bit needs to be materialized into a node
        while (l1 != nullptr || l2 != nullptr || carry != 0) {
            int sum = carry;

            if (l1 != nullptr) {
                sum += l1->val;
                l1 = l1->next;
            }

            if (l2 != nullptr) {
                sum += l2->val;
                l2 = l2->next;
            }

            // Inductive state transition:
            carry = sum / 10;                     // c_{k+1} = floor(sigma_k / 10)
            tail->next = new ListNode(sum % 10);  // s_k     = sigma_k mod 10
            tail = tail->next;
        }

        return dummy.next;
    }
};

Approach 2 · Recursive Structural Induction

Directly translates the inductive mathematical specification into functional recursion. Each stack frame computes one digit $s_k$ and passes carry $c_{k+1}$ to the recursive call:

C++

class SolutionRecursive {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2, int carry = 0) {
        // Base case: both streams exhausted and no lingering carry
        if (!l1 && !l2 && carry == 0) {
            return nullptr;
        }

        int sum = carry;
        if (l1) { sum += l1->val; l1 = l1->next; }
        if (l2) { sum += l2->val; l2 = l2->next; }

        // Inductively construct node and recurse for the next positional rank 10^{k+1}
        ListNode* current = new ListNode(sum % 10);
        current->next = addTwoNumbers(l1, l2, sum / 10);

        return current;
    }
};

Approach	Time Complexity	Auxiliary Space	Call Stack Depth	Allocated Nodes
Iterative Sentinel (Optimal)	O(max(m, n))	O(1)	O(1)	≤ max(m, n) + 1
Recursive Induction	O(max(m, n))	O(max(m, n)) stack	≤ max(m, n) + 1	≤ max(m, n) + 1

06

Advanced Follow-up · In-Place Node Mutation

In memory-constrained embedded systems or hot allocator paths, dynamically allocating $\max(m, n) + 1$ new nodes invokes the OS heap allocator (malloc / operator new), which introduces latency and cache misses.

If caller contract permits mutating the input lists, we can reuse either l1 or l2 in place by overwriting node->val = sum % 10. Only if a final carry exists ( $c_K = 1$ ) does a single node need to be allocated at the tail, reducing heap allocations from $\mathcal{O}(\max(m, n))$ to at most $1$ !

2. Add Two Numbers

Problem Statement

Mathematical Representation · Little-Endian Positional Numeral System

Formal Carry Recurrence & Invariant Proof

Execution State Trace · Cascading Ripple Carry

Sentinel (Dummy Head) Pattern & Memory Semantics

Optimal C++ Implementations

Approach 1 · Iterative with Sentinel Pointer (Production Standard)

Approach 2 · Recursive Structural Induction

Advanced Follow-up · In-Place Node Mutation

Comments (0)