Skip to content

Volume ITechnology

4.9.6 — Add Two Numbers ​

LeetCode 2 · Medium

The problem ​

You are given two linked lists. Each one stores a whole number, one digit per node, with the ones digit first. So the number 342 is stored as 2 → 4 → 3. Add the two numbers and return the sum as a linked list in the same backwards form.

l1 = 2 → 4 → 3        (342)
l2 = 5 → 6 → 4        (465)
sum = 7 → 0 → 8       (807)

l1 = 9 → 9 → 9 → 9    (9999)
l2 = 9 → 9            (99)
sum = 8 → 9 → 0 → 0 → 1   (10098)

Each list has between 1 and 100 nodes, so a number can have up to 100 digits. There are no leading zeros, except for the number 0 itself.

What the problem is really asking ​

How did you learn to add numbers at school? Line them up on the right. Add the ones column. If it comes to 10 or more, write the last digit and carry 1 into the next column. Then add the tens column, plus the carry. And so on, right to left.

Addition starts at the ones digit and moves toward the bigger digits. The lists here are stored ones digit first. So the order of the lists is exactly the order of column addition. The backwards storage is a gift, not an obstacle.

So the real question is just: walk both lists together, adding column by column, and carry correctly.

The brute force, and where it breaks ​

Turn each list into an ordinary number, add them, and turn the sum back into a list.

python
def addTwoNumbers(l1, l2):
    def to_int(node):
        num, place = 0, 1
        while node:
            num += node.val * place      # each digit is worth 10 times the last
            place *= 10
            node = node.next
        return num
    total = to_int(l1) + to_int(l2)
    dummy = tail = ListNode()
    for ch in reversed(str(total)):      # ones digit first
        tail.next = ListNode(int(ch))
        tail = tail.next
    return dummy.next

In Python this happens to work, because Python whole numbers can be as large as you like. In most other languages a 100-digit number is far too large for an ordinary number type, so the conversion overflows and gives a wrong answer. TypeScript numbers lose accuracy past about 16 digits.

The flaw in one sentence: it relies on the language holding a 100-digit number, when column addition with a carry needs only one digit at a time.

The idea ​

Walk both lists at once, one column per step.

  1. Start the column total with the carry from the previous column.
  2. Add this list's digit if it still has one, and that list's digit if it still has one.
  3. Split the total into a new carry (the tens part) and a digit (the ones part).
  4. Attach a new node with that digit to the result.

Keep going while either list has digits left, or there is still a carry.

The solution ​

python
class Solution:
    def addTwoNumbers(self, l1, l2):
        dummy = ListNode()                      # (1)
        tail = dummy
        carry = 0                               # (2)

        while l1 or l2 or carry:                # (3)
            total = carry                       # (4)
            if l1:                              # (5)
                total += l1.val
                l1 = l1.next
            if l2:
                total += l2.val
                l2 = l2.next

            carry, digit = divmod(total, 10)    # (6)
            tail.next = ListNode(digit)         # (7)
            tail = tail.next

        return dummy.next                       # (8)
ts
function addTwoNumbers(l1: ListNode | null, l2: ListNode | null): ListNode | null {
  const dummy = new ListNode();                 // (1)
  let tail = dummy;
  let carry = 0;                                // (2)

  while (l1 || l2 || carry) {                   // (3)
    let total = carry;                          // (4)
    if (l1) { total += l1.val; l1 = l1.next; }  // (5)
    if (l2) { total += l2.val; l2 = l2.next; }

    carry = Math.floor(total / 10);             // (6)
    tail.next = new ListNode(total % 10);       // (7)
    tail = tail.next;
  }

  return dummy.next;                            // (8)
}

Line by line ​

(1) A dummy head and a tail pointer. The dummy is a fake first node, so the first real digit is attached in the same way as every other digit. This is the habit from 4.9.2.

(2) The carry starts at 0, because there is no column before the ones column.

(3) Keep going while anything is left. This one line handles three different situations.

  • l1 or l2 still has digits. The lists can be different lengths. Once the shorter one runs out, it just adds nothing.
  • carry is not zero. This is the case people forget. Take 5 + 5. Both lists have one digit. After the first column, both lists are empty, but the carry is 1, and a final digit 1 must still be written. Without or carry, the answer would be 0 instead of 0 → 1, which reads as 10.

Putting all three into the loop condition means there is no separate "finish the longer list" loop, and no "check the carry at the end" step.

(4) Start the column total with the carry.

(5) Add each list's digit, if it has one, and move that list forward.

(6) Split the total. divmod(total, 10) returns two answers at once: how many whole tens fit into total (the new carry), and what is left over (the digit to write). For a total of 17, that is (1, 7).

The carry is always 0 or 1. The biggest possible total is 9 + 9 + 1 = 19, and 19 holds only one ten.

In TypeScript there is no divmod. Math.floor(total / 10) gives the carry, and total % 10 gives the remainder, which is the digit.

(7) Attach a new node for this digit, and move tail onto it.

(8) Skip the dummy and return the real first digit.

Trace ​

Take l1 = 9 → 9 (99) and l2 = 1 (1). The answer should be 100.

Columnl1 digitl2 digitCarry inTotalDigit writtenCarry out
19101001
29—11001
3——1110

The result is 0 → 0 → 1, which reads backwards as 100. ✓ Column 3 only happened because of or carry in line (3).

Complexity, derived ​

Let n and m be the lengths of the two lists.

Time. Each turn of the loop handles one column. There are as many columns as the longer list, plus possibly one more for a final carry. So the loop runs \max(n, m) or \max(n, m) + 1 times, with constant work each time. That is O(\max(n, m)). Read \max(n, m) as "the larger of n and m".

Space. The answer list has \max(n, m) or \max(n, m) + 1 nodes. That memory is the answer itself, so it cannot be avoided. Apart from it, we use a few variables, so the extra memory is O(1).

Edge cases ​

  • Different lengths, like 9999 + 99. The shorter list stops adding after it runs out.
  • A final carry, like 5 + 5. Handled by or carry.
  • A zero, like 0 + 0. One column, total 0, and the answer is 0.
  • A long chain of carries, like 999 + 1. Every column carries, and a new final digit appears.

The forward-order version ​

Add Two Numbers II (LeetCode 445) stores the digits biggest first, like 3 → 4 → 2 for 342, and does not let you reverse the input lists. Now addition must start from the end of each list, which a singly linked list cannot walk to.

There are three ways out.

  1. Reverse both lists, add as on this page, then reverse the answer. Simplest, but only if you are allowed to change the input.
  2. Push both lists' digits onto two stacks. Popping a stack gives the digits ones-first, which is this page's problem again. It uses O(n) memory but never changes the input.
  3. Recurse, letting the calls finish from the last digit back to the first.

The stack version is the usual answer. It shows a stack used for nothing more than reversing the order you process things in.

Variations you will meet ​

  • Plus One. Add 1 to a number stored as a list of digits. The only interesting case is all nines. See 4.28.5.
  • Multiply Strings. Multiply two numbers stored as text, with the same carry rule, now in a grid of columns. See 4.28.7.
  • Big-number libraries. Python's own whole numbers work this way inside. They store a big number as a list of chunks and add them column by column with a carry, just in a much bigger base than 10.

The general lesson: digit-by-digit arithmetic is a loop over columns, with a carry that must survive past the end of both inputs.

What the interviewer will push on ​

"What if the lists are different lengths?" The if l1 and if l2 checks. The shorter list stops adding.

"What if there is a carry at the very end?" The or carry in the loop condition. Give 5 + 5 as the example.

"Why not turn the lists into numbers and add?" Overflow in most languages. In Python it would work, which is a good moment to say that you know the difference between what a language allows and what an algorithm should rely on.

"What if the digits were stored biggest first?" The three options above, with two stacks as the usual answer.

One thing to volunteer: point out that the loop condition covers all three ways the addition can end, so no clean-up code is needed after the loop.

Next: 4.9.7 Linked List Cycle. Two pointers at different speeds, and a proof that they must meet.

Combine chapters into one PDF

Pick the chapters you want. They print in the order you pick them.

Volume I — Technology
Part 0 — Retention & Notation
Part 1 — Foundations of Computation
Part 2 — Operating Systems
2.1 The Kernel
2.2 Processes
2.3 Threads & Scheduling
2.4 Concurrency Under the Hood
2.5 Memory Management
2.6 File Systems
2.7 Input/Output
2.8 Linux for Engineers
2.9 Windows & macOS in Practice
Part 3 — Languages, Compilers & Runtimes
3.6 JavaScript & V8
3.7 TypeScript
3.8 Node.js Internals
3.13 Python & CPython
3.14 FastAPI & Production Python
Part 4 — Data Structures & Algorithms
4.0 Classic Problems — Before NeetCode
4.4 Arrays & Hashing — Problems
4.5 Two Pointers
4.6 Sliding Window
4.8 Stack — Problems
4.9 Linked List — Problems
4.11 Binary Search — Problems
4.13 Trees
4.14 Tree — Problems
4.15 Trie — Problems
4.17 Heap — Problems
4.18 Backtracking — Problems
4.19 Graphs
4.20 Graph — Problems
4.21 Advanced Graph — Problems
4.23 1-D DP — Problems
4.24 2-D DP — Problems
4.26 Greedy — Problems
4.27 Interval — Problems
4.28 Math & Geometry — Problems
4.30 Bit Manipulation — Problems
Part 5 — Networking & the Web
5.3 IP
5.4 Transport
5.6 HTTP
Part 6 — Frontend Engineering
6.1 Browser Internals
6.2 HTML & CSS Mastery
6.3 JavaScript in the Browser
6.4 React, from First Component to Full Shop
6.5 Frameworks & Rendering
6.8 UI Engineering & Patterns
Part 7 — Databases & Storage
7.2 SQL Mastery
7.3 Storage Engine Internals
7.4 Transactions
7.5 NoSQL Taxonomy
7.8 Analytics & Big Data
Part 8 — Security, Identity & Cryptography
8.2 Cryptography
8.3 Protocols of Trust
8.4 Identity: AuthN & AuthZ
8.5 Application Security
8.6 Infrastructure Security
Part 9 — Software Design (LLD)
9.2 OOP Foundations
9.3 Design Principles
9.4 Design Patterns
9.5 Concurrency
9.6 API Design
9.7 LLD Interview Machines
9.9 Node/Express Production Playbook
Part 10 — Distributed Systems & HLD
10.7 Consistency & Consensus
10.8 Messaging & Microservices
10.14 Caching
Building blocks from the design seat
Part 11 — System Design Case Studies
Part 12 — AI & ML Engineering
12.1 What AI Engineering Is
12.2 The Math You Need
12.3 Classical Machine Learning
12.4 Data for ML
12.5 Deep Learning
12.6 Embeddings & Vector Search
12.7 Transformers & LLMs
12.8 Building with LLMs
12.9 Retrieval-Augmented Generation
12.10 Agents
12.11 Adapting Models
12.12 Production AI
12.13 Multimodal AI
12.14 AI Security & Governance
12.15 Case Studies & Capstone
Part 13 — Cloud, DevOps & Infrastructure
13.11 Git, from First Commit to Team Workflow
Part 14 — Containers: Docker & Kubernetes
14.1 Foundations
14.2 Docker
14.3 Kubernetes
14.4 Kubernetes on Azure
Part 15 — The Craft & Career
Nothing picked yet