Problem 2

Abstract / Summary

You are given two linked lists representing numbers and must return a new linked list that is their sum.

Note

The full problem description, including helpful examples, can be found on LeetCode.

C++ 0002.cpp

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        vector<int> sum;
        int carry = 0;
        while (l1 || l2)
        {
            sum.push_back(carry);
            if (l1)
            {
                sum.back() += l1->val;
                l1 = l1->next;
            }
            if (l2)
            {
                sum.back() += l2->val;
                l2 = l2->next;
            }

            carry = sum.back() / 10;
            sum.back() %= 10;
        }

        if (carry > 0)
            sum.push_back(carry);

        ListNode* next = nullptr;
        for (int i = sum.size() - 1; i >= 0; i--)
        {
            auto current = new ListNode(sum[i], next);
            next = current;
        }
        return next;
    }
};
35 lines | 825 bytes | submitted August 7, 2023 | GitHub   tab size 4

Difficulty

This problem is ranked as
easy medium hard

and has an acceptance rate of about 49% (10+ million submissions).

Typical patterns to solve this problem:
  • Linked List
  • Math
  • Recursion
I solved 663 easy, 1250 medium and 309 hard problems

AI Disclaimer

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.
LeetCode profile | GitHub repo

Code Walkthrough

Overview

The provided implementation solves the classic “add two numbers represented by linked lists” problem. It traverses the input lists, accumulates digit sums in a temporary vector while managing carry propagation, and finally constructs a new linked list representing the result in forward order. The algorithm is deterministic and operates in a single pass over each input list, followed by a reverse iteration over the collected digits to build the output list.

Core Steps

Digit Accumulation

The algorithm begins by initializing an empty vector<int> named sum and a carry variable set to zero. A loop continues as long as at least one of the input pointers (l1 or l2) is non-null. Inside the loop a new element is appended to sum containing the current carry value. The code then conditionally adds the value from each list node to the most recent element of sum. After the optional additions, the carry for the next iteration is computed by integer division of the last element by ten, and the element itself is reduced to a single digit by taking the remainder modulo ten.

vector<int> sum;
int carry = 0;
while (l1 || l2)
{
    sum.push_back(carry);
    if (l1)
    {
        sum.back() += l1->val;
        l1 = l1->next;
    }
    if (l2)
    {
        sum.back() += l2->val;
        l2 = l2->next;
    }

    carry = sum.back() / 10;
    sum.back() %= 10;
}

Final Carry Handling

When the main loop exits, a residual carry may remain. The implementation checks for a positive carry and, if present, appends it as an additional digit to the sum vector. This step guarantees that the most significant digit is correctly represented when the final addition produces an overflow.

if (carry > 0)
    sum.push_back(carry);

List Construction in Forward Order

The collected digits are stored in reverse order (least significant digit first). To produce a linked list that matches the required forward order, the code iterates backward over the sum vector. For each digit, a new ListNode is allocated with the digit value and a pointer to the previously created node (next). The next pointer is then updated to reference the newly created node. After the loop completes, next points to the head of the fully constructed list.

ListNode* next = nullptr;
for (int i = sum.size() - 1; i >= 0; i--)
{
    auto current = new ListNode(sum[i], next);
    next = current;
}
return next;

Edge Cases Addressed

The implementation gracefully handles several boundary conditions without additional branching:

  • Empty Input Lists - If both l1 and l2 are null, the while loop never executes, carry remains zero, and the final list returned is null, representing the numeric value zero.
  • Unequal Lengths - The loop condition while (l1 || l2) ensures that traversal continues until the longer list is exhausted. The conditional blocks add values only when the corresponding pointer is non-null, effectively treating missing digits as zero.
  • Final Carry Overflow - After processing all nodes, a remaining carry greater than zero triggers an extra push to sum, guaranteeing that an additional most-significant digit is emitted when the sum exceeds the original digit count (e.g., adding 9 → 9 yields 18).
  • Single-Digit Result - When the sum fits within a single digit, the vector contains exactly one element, and the reverse construction loop creates a solitary node, correctly representing the result.

Performance Optimizations

The code exhibits several efficiency considerations:

  • In-Place Carry Integration - By inserting the current carry directly into the newly pushed element of sum, the algorithm avoids a separate temporary variable for the digit sum, reducing memory traffic.
  • Minimal Node Allocation - The output list is built in a single backward pass, allocating each node exactly once. No intermediate list structures or additional traversals are required.
  • Vector Preallocation Avoidance - The use of push_back on a vector<int> leverages its amortized constant-time growth, which is sufficient for the typical size of the input lists. The vector’s contiguous storage also benefits cache locality during the reverse iteration that constructs the final list.
  • Early Termination of Traversal - The loop condition checks both pointers simultaneously, allowing the traversal to stop as soon as the longer list ends, rather than iterating a fixed number of steps.

Overall, the solution balances clarity with efficient use of standard containers and straightforward pointer manipulation, delivering a concise and performant addition routine for linked-list based integer representations.

written by openai gpt

ELI5 - Simplified Explanation

Imagine two trains made of blocks, where each block has a number written on it. The task is to add the numbers on the blocks together, just like adding toys in a pile. The code starts by looking at the first block from each train and adding their numbers together. If the total is ten or more, a little bit gets saved to carry over to the next pair of blocks, similar to how counting on fingers works when the number gets too big for one hand.

This process continues block by block until all the numbers have been added up carefully. If there is still a small bit left over at the end after the last blocks are finished, it gets added as one final block. Once all the math is done and the new numbers are ready, the code builds a brand new train of blocks to hold the results. It goes through the list of answers and links each new block to the one that came before it, creating a perfect line of blocks that tells the final total.

written by google gemini

Code Quality

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):
n = 30 | median = 7 | μ = 6.40 | σ = 1.08

Complexity Analysis

Time: linear
As a rule of thumb, the maximum input size for one second execution time is
  • factorial: up to 10 elements
  • exponential: up to 20 elements
  • polynomial: a few thousand elements
  • loglinear: up to 100,000 elements
  • linear: a few million elements
  • logarithmic: a billion elements
  • constant: practically unlimited
generated automatically

Other Solutions

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)
author
author solutions
www AlgoMonster C++ Java Python TS
WalkCCC C++ Java Python
leetcode.ca C++ Java Python C C# Rust JS TS Ruby Go Nim PHP Swift
LeetcodeHelp C++ Java Python
MemoryLimitExceeded C++ Python
Progiez C++ Java Python
github AdelDaniel Dart
aylei Rust
begeekmyfriend C
BigEggStudy C#
black-shadows C++
bujosa Rust
chandansgowda Python
charles-wangkai Java
chenyanzhe C++
Dijkstra-Edu Java
DimitrisJim C
everthis JS
fartem Ruby
FelixFan1122 C#
fengvyi C++
fpdjsns C++
fsq C++
gaosq0604 Python
gouthampradhan Java
halfrost Go
haoel C++
JoshCrozier JS
keineahnung2345 C++
Krazune C
lennylxx C
linouk23 C++
lkwq007 Python
luangong C++ TS
pruthvikp Python
qiyuangong Java
ruoru Rust
Shamik07 Dart
shreymehul C#
sonugiri1043 C++
suxrobGM C#
varunu28 Java
vli02 C
vthwang Java
XiaotaoGuo C++
yuanliu666 Kotlin
YuriSpiridonov Python
zfang399 C++
AlgoMonster C++, Python, Java, TypeScript
WalkCCC C++, Python, Java
leetcode.ca C, C++, C#, Go, Java, JavaScript, Nim, PHP, Python, Ruby, Rust, Swift, TypeScript
LeetcodeHelp C++, Java, Python
MemoryLimitExceeded Python, C++
Progiez C++, Java, Python
AdelDaniel Dart
aylei Rust
begeekmyfriend C
BigEggStudy C#
black-shadows C++, C++
bujosa Rust
chandansgowda Python
charles-wangkai Java
chenyanzhe C++
Dijkstra-Edu Java
DimitrisJim C
everthis JavaScript
fartem Ruby
FelixFan1122 C#
fengvyi C++
fpdjsns C++
fsq C++
gaosq0604 Python
gouthampradhan Java
halfrost Go
haoel C++
JoshCrozier JavaScript
keineahnung2345 C++
Krazune C
lennylxx C
linouk23 C++
lkwq007 Python
luangong C++, TypeScript
pruthvikp Python
qiyuangong Java
ruoru Rust
Shamik07 Dart
shreymehul C#
sonugiri1043 C++
suxrobGM C#
varunu28 Java
vli02 C
vthwang Java
XiaotaoGuo C++
yuanliu666 Kotlin
YuriSpiridonov Python
zfang399 C++
71 links | 48 authors | 15 languages

Videos

These are a few popular YouTube videos for this problem:
YouTube video 'Add Two Numbers - Leetcode 2 - Python'
NeetCode 10 mins
Add Two Numbers - Leetcode 2 - Python
YouTube video 'Add Two Numbers (LeetCode 2) | Full solution with diagrams | EASIEST EVER | Study Algorithms'
Nikhil Lohia 14 mins
Add Two Numbers (LeetCode 2) | Full solution with diagrams | EASIEST EVER | Study Algorithms
YouTube video 'Add Two Numbers Python Solution - LeetCode #2'
Professor Oakes 7 mins
Add Two Numbers Python Solution - LeetCode #2
YouTube video 'Add Two Numbers | Leetcode 2 | C++'
Knowledge Center 12 mins
Add Two Numbers | Leetcode 2 | C++
YouTube video 'DSA Phir se with Sumeet | Leetcode 2 | Add two numbers'
Pepcoding 28 mins
DSA Phir se with Sumeet | Leetcode 2 | Add two numbers
YouTube video 'Add Two Numbers | Leet code 2 | Theory explained + Python code'
Sai Anish Malla 17 mins
Add Two Numbers | Leet code 2 | Theory explained + Python code
YouTube video '[Java] Leetcode 2. Add Two Numbers [LinkedList #1]'
Eric Programming 9 mins
[Java] Leetcode 2. Add Two Numbers [LinkedList #1]
YouTube video 'Add two numbers represented by linked lists 🔥 | Amazon | Microsoft'
Ayushi Sharma 18 mins
Add two numbers represented by linked lists 🔥 | Amazon | Microsoft
YouTube video 'add two numbers leetcode | leetcode 2 | linked list | google | facebook | microsoft'
Naresh Gupta 7 mins
add two numbers leetcode | leetcode 2 | linked list | google | facebook | microsoft
YouTube video 'Add Two Numbers  - LeetCode 2 - Python'
Deepti Talesra 14 mins
Add Two Numbers - LeetCode 2 - Python
YouTube video 'Leetcode 2 - Add Two Numbers (JAVA Solution Explained!)'
LC Bear 7 mins
Leetcode 2 - Add Two Numbers (JAVA Solution Explained!)
YouTube video '2. Add Two Numbers | Day 021 | Linked List | Hottest Question in Linked List'
Aryan Mittal 9 mins
2. Add Two Numbers | Day 021 | Linked List | Hottest Question in Linked List
YouTube video '2. Add Two Numbers || NEETCODE 150'
TechWithSaumya 12 mins
2. Add Two Numbers || NEETCODE 150
YouTube video 'LeetCode 2 | Add Two Numbers | C# Solution | Linked List Manipulation |'
Code Scribbler 5 mins
LeetCode 2 | Add Two Numbers | C# Solution | Linked List Manipulation |
YouTube video 'Leetcode: Add Two Numbers (Java)'
Dave Kirkwood 9 mins
Leetcode: Add Two Numbers (Java)
YouTube video 'Coding interview Question - leetcode python - add Two Numbers'
One Code Man 6 mins
Coding interview Question - leetcode python - add Two Numbers
YouTube video 'Add Two Numbers || LinkedList 7 || Placement Preparation Series || LeetCode 2 || C++ ||'
Bro Coders 11 mins
Add Two Numbers || LinkedList 7 || Placement Preparation Series || LeetCode 2 || C++ ||
YouTube video 'Leetcode 2 Add Two Numbers (Java)'
TheAnalyticGuy 8 mins
Leetcode 2 Add Two Numbers (Java)
YouTube video 'Add Two Numbers | Leetcode 2 | Live coding session'
Coding Decoded 10 mins
Add Two Numbers | Leetcode 2 | Live coding session
YouTube video 'LeetCode 2. Add Two Numbers given as Linked List | LeetCode | Medium'
Cherry Coding [IIT-G] 8 mins
LeetCode 2. Add Two Numbers given as Linked List | LeetCode | Medium
20 videos   did my crawler come up with invalid videos ? drop me a line.

Similar Problems

3 similar problems

Solved On The Same Day

40 easy 30 medium 1 hard
72 solutions   August 7, 2023

Extra

There are a few extra pages giving you some insights into my setup:
  • Tech Stack - my development environment and tools
  • AI - how AI helped me create this website (NOT solving the problems)
  • Progress - progression over time
  • Quality - code quality