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;
}
};
Difficulty
and has an acceptance rate of about 49% (10+ million submissions).
Typical patterns to solve this problem:
- Linked List
- Math
- Recursion
AI Disclaimer
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.
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
l1andl2are null, the while loop never executes,carryremains 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
carrygreater than zero triggers an extra push tosum, 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
carrydirectly into the newly pushed element ofsum, 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_backon avector<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.
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.
Code Quality
Complexity Analysis
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
Other Solutions
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++ |
Videos
Similar Problems
- problem 43: Multiply Strings
- problem 371: Sum of Two Integers
- problem 445: Add Two Numbers II
Solved On The Same Day
- problem 13: Roman to Integer
- problem 21: Merge Two Sorted Lists
- problem 28: Find the Index of the First Occurrence in a String
- problem 35: Search Insert Position
- problem 58: Length of Last Word
- problem 66: Plus One
- problem 67: Add Binary
- problem 69: Sqrt(x)
- problem 70: Climbing Stairs
- problem 206: Reverse Linked List
- problem 242: Valid Anagram
- problem 278: First Bad Version
- problem 283: Move Zeroes
- problem 367: Valid Perfect Square
- problem 374: Guess Number Higher or Lower
- problem 389: Find the Difference
- problem 441: Arranging Coins
- problem 459: Repeated Substring Pattern
- problem 509: Fibonacci Number
- problem 657: Robot Return to Origin
- problem 682: Baseball Game
- problem 704: Binary Search
- problem 709: To Lower Case
- problem 744: Find Smallest Letter Greater Than Target
- problem 746: Min Cost Climbing Stairs
- problem 860: Lemonade Change
- problem 896: Monotonic Array
- problem 976: Largest Perimeter Triangle
- problem 1137: N-th Tribonacci Number
- problem 1232: Check If It Is a Straight Line
- problem 1275: Find Winner on a Tic Tac Toe Game
- problem 1351: Count Negative Numbers in a Sorted Matrix
- problem 1491: Average Salary Excluding the Minimum and Maximum Salary
- problem 1502: Can Make Arithmetic Progression From Sequence
- problem 1523: Count Odd Numbers in an Interval Range
- problem 1539: Kth Missing Positive Number
- problem 1572: Matrix Diagonal Sum
- problem 1672: Richest Customer Wealth
- problem 1768: Merge Strings Alternately
- problem 1822: Sign of the Product of an Array
- problem 5: Longest Palindromic Substring
- problem 33: Search in Rotated Sorted Array
- problem 34: Find First and Last Position of Element in Sorted Array
- problem 43: Multiply Strings
- problem 50: Pow(x, n)
- problem 54: Spiral Matrix
- problem 62: Unique Paths
- problem 63: Unique Paths II
- problem 64: Minimum Path Sum
- problem 73: Set Matrix Zeroes
- problem 74: Search a 2D Matrix
- problem 120: Triangle
- problem 139: Word Break
- problem 153: Find Minimum in Rotated Sorted Array
- problem 198: House Robber
- problem 221: Maximal Square
- problem 275: H-Index II
- problem 279: Perfect Squares
- problem 300: Longest Increasing Subsequence
- problem 436: Find Right Interval
- problem 445: Add Two Numbers II
- problem 528: Random Pick with Weight
- problem 540: Single Element in a Sorted Array
- problem 611: Valid Triangle Number
- problem 658: Find K Closest Elements
- problem 852: Peak Index in a Mountain Array
- problem 981: Time Based Key-Value Store
- problem 1041: Robot Bounded In Circle
- problem 1146: Snapshot Array
- problem 2300: Successful Pairs of Spells and Potions
- problem 154: Find Minimum in Rotated Sorted Array II
Extra
- 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