Abstract / Summary

Add two numbers given as reversed linked lists and return the result as a reversed linked list.

Note

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

This problem is ranked as

and has an acceptance rate of about 63% (900k+ submissions).

Typical patterns to solve this problem:

• Linked List
• Math
• Stack

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.

Overview

The presented implementation solves the classic problem of adding two non-negative integers where each digit is stored in a singly-linked list node. The digits are stored in forward order, meaning the most significant digit appears at the head of the list. The algorithm first extracts the digits into random-access containers, equalizes their lengths, then performs a right-to-left addition while propagating the carry. The result is built as a new linked list in forward order and returned to the caller.

Input Normalization

The first phase walks each input list and copies the node values into a vector<int>. This conversion provides constant-time indexed access, which simplifies the later addition step.

vector<int> a, b;
while (l1)
{
    a.push_back(l1->val);
    l1 = l1->next;
}
while (l2)
{
    b.push_back(l2->val);
    l2 = l2->next;
}

By iterating until the pointer becomes nullptr, the code gracefully handles empty input lists, producing an empty vector for a nullptr argument.

Size Equalization

Because the addition proceeds from the least significant digit, the two vectors must share the same length. The implementation pads the shorter vector with leading zeros. This ensures that each index i refers to digits that align by significance.

if (a.size() < b.size())
    a.insert(a.begin(), b.size() - a.size(), 0);
if (b.size() < a.size())
    b.insert(b.begin(), a.size() - b.size(), 0);

The use of insert at the beginning preserves the original order of the more significant digits while extending the vector to the required size.

Summation Loop

The core addition runs a reverse for loop over the vectors, accumulating the sum of corresponding digits together with any carry from the previous iteration. The carry is computed by integer division, and the digit to store is obtained via modulus. A new ListNode is allocated for each digit, linking it to the previously created node via the next pointer. This builds the result list from tail to head without needing a separate traversal to locate the tail.

int carry = 0;
ListNode* next = nullptr;
for (int i = a.size() - 1; i >= 0; i--)
{
    auto sum = carry + a[i] + b[i];
    carry = sum / 10;
    auto current = new ListNode(sum % 10, next);
    next = current;
}

The constructor ListNode(value, next) directly sets the next field, avoiding an extra assignment after node creation.

Final Carry Handling

After processing all digit positions, a leftover carry indicates an overflow beyond the most significant digit. The algorithm checks for this condition and, if necessary, creates an additional node that becomes the new head of the result list.

if (carry > 0)
    next = new ListNode(carry, next);

This step ensures that inputs such as 9 -> 9 plus 1 correctly produce 1 -> 0 -> 0.

Edge Cases Handled

The code naturally accommodates several boundary situations. When both input lists are empty, the vectors remain empty, the loop body is skipped, and the final carry check yields nullptr, representing a zero result. When one list is longer than the other, the padding logic equalizes lengths, allowing the addition loop to treat both vectors uniformly. A final carry greater than zero is explicitly turned into a new leading node, covering cases where the sum introduces an extra digit. The use of while (l1) and while (l2) loops also prevents dereferencing null pointers, safely terminating at the end of each list.

Performance Optimizations

The algorithm leverages random-access vectors to avoid repeated traversal of the linked lists during addition. By converting the lists to vectors, the addition step can index digits directly, which is more cache-friendly than walking two linked lists in parallel. The construction of the result list proceeds in reverse order, linking each newly created node to the previously built sub-list. This eliminates the need for a tail pointer or a separate pass to reverse the list, thereby reducing the number of pointer updates and memory allocations. Additionally, the ListNode constructor that accepts both value and next pointer consolidates node initialization into a single operation, minimizing the overhead of separate field assignments.

Imagine you have two long trains made of brightly colored blocks. Each block has a special number painted on it. This code starts by taking every single block from both trains and lining them up in two rows on a table so they are very easy to see.

Since the trains might be different lengths, the code adds invisible empty blocks to the shorter train so both rows have exactly the same number of blocks. Now comes the fun part. Starting from the very last blocks at the end of the rows, the code adds the numbers on the two blocks together. If the two numbers make a big pile that is ten or higher, the code puts a tiny sticky note called a carry in the next spot to remember the extra part for the next step.

As it works backward toward the front of the trains, it creates a brand new train of blocks. Each new block keeps the right amount from the addition and attaches itself to the piece made before it. If there is still a sticky note left over after checking all the blocks, one final piece is added to the very front of the new train to hold that last bit. This finished chain of blocks is the answer that shows the sum.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

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

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++	Python	Java							TS
	WalkCCC	C++	Python	Java
	leetcode.ca	C++	Python	Java			Rust			Go	TS
	LeetcodeHelp	C++	Python	Java
	Progiez	C++	Python	Java
github	BigEggStudy					C#
	black-shadows	C++
	charles-wangkai			Java
	everthis				JS
	fartem							Ruby
	halfrost									Go
	JoshCrozier				JS
	keineahnung2345	C++
	linouk23	C++
	lkwq007		Python
	ruoru						Rust
	suxrobGM					C#
	trung-hn		Python
	varunu28			Java
	vthwang			Java
	yuanliu666								Kotlin
	YuriSpiridonov		Python
	zfang399	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python, Rust, TypeScript
LeetcodeHelp	C++, Java, Python
Progiez	C++, Java, Python
BigEggStudy	C#
black-shadows	C++, C++
charles-wangkai	Java
everthis	JavaScript
fartem	Ruby
halfrost	Go
JoshCrozier	JavaScript
keineahnung2345	C++
linouk23	C++
lkwq007	Python
ruoru	Rust
suxrobGM	C#
trung-hn	Python
varunu28	Java
vthwang	Java
yuanliu666	Kotlin
YuriSpiridonov	Python
zfang399	C++

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