Skip to main content
Talentd

Add Two Numbers - Solution & Explanation

MediumLinked ListMathRecursion32 min readAsked at: Amazon, Microsoft, Apple +34
Practice this problem

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:

Input: l1 = [2,4,3], l2 = [5,6,4]
Output: [7,0,8]
Explanation: 342 + 465 = 807.

Example 2:

Input: l1 = [0], l2 = [0]
Output: [0]

Example 3:

Input: l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
Output: [8,9,9,9,0,0,0,1]

 

Constraints:

  • The number of nodes in each linked list is in the range [1, 100].
  • 0 <= Node.val <= 9
  • It is guaranteed that the list represents a number that does not have leading zeros.

Approach Overview

Problem Overview: Two non-empty linked lists represent two non‑negative integers. Each node stores a single digit, and digits are stored in reverse order. You add the two numbers and return the sum as a new linked list while correctly handling digit carry.

Approach 1: Iterative Linked List Addition (O(n) time, O(1) extra space)

Traverse both lists simultaneously while maintaining a carry value. At each step, read the current digit from each list (use 0 if a list is exhausted), compute sum = x + y + carry, store sum % 10 as the new node, and update carry = sum // 10. Move both pointers forward and append the new node to the result list. This works because digits are already stored in reverse order, so addition proceeds exactly like manual column addition from least significant digit to most.

The loop continues while either list still has nodes or a carry remains. A dummy head node simplifies result construction and avoids special handling for the first node. Time complexity is O(max(m,n)) because each node is processed once, and extra space is O(1) excluding the output list. This approach relies heavily on pointer manipulation in a linked list and basic math operations for carry propagation.

Approach 2: Recursive Digit Addition (O(n) time, O(n) space)

The same addition logic can be expressed recursively. Each recursive call processes one pair of nodes and returns the resulting node for that digit. Compute the digit sum and carry exactly as in the iterative method, create a node with sum % 10, and recursively compute the next node using the remaining list nodes and updated carry.

The recursion stops when both lists are exhausted and no carry remains. If a carry still exists after the final digits, create one last node to store it. Time complexity remains O(max(m,n)) since each digit is processed once. Space complexity becomes O(n) due to the call stack used by recursion. This version is concise and elegant but less memory‑efficient than the iterative solution.

Recommended for interviews: The iterative approach is what most interviewers expect. It demonstrates comfort with linked list traversal, pointer manipulation, and carry management. Explaining the recursive version afterward shows deeper understanding of the same logic expressed through recursion. Implementing the iterative solution correctly without edge‑case bugs (different list lengths, leftover carry) is usually the key evaluation point.

Approach 1: Iterative Approach

This approach involves iterating through both linked lists, node by node, adding corresponding values along with any carry from the previous addition. The result at each step is appended to a new linked list. If one list is longer than the other, the iteration continues on the longer list alone. A final check is done to handle any remaining carry.

This C implementation employs a dummy head node to start building the resultant list. A 'carry' variable is used to keep track of any overflow beyond a single digit, which is added to the next higher digit. The values are summed, and their result is split into carry and remainder, which becomes the node value. The iteration continues until both input lists are exhausted. The remaining carry is checked to append another node if needed.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(max(m, n)) where m and n are the lengths of the input lists. This is because we iterate through each node exactly once.
Space Complexity: O(max(m, n)) to store the resulting list.

Try this approach in the editor →

Approach 2: Recursive Approach

The recursive approach solves the problem by recursing down the linked lists, accumulating values with carry and constructing the result linked list from the returned values from child calls. Each recursive call processes one pair of nodes from the lists, similar to how you would process each position in a sum independently in the iterative version.

In this C solution, we define a helper function addTwoNumbersRecursive that takes the two input lists and a carry. The function recursively creates new nodes based on the summed values ensuring that carry is also considered. The base case returns NULL when ends of both lists and no carry remain.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(max(m, n))
Space Complexity: O(max(m, n)) because of the recursion stack.

Try this approach in the editor →

Approach 3: Simulation

We traverse two linked lists l_1 and l_2 at the same time, and use the variable carry to indicate whether there is a carry.

Each time we traverse, we take out the current bit of the corresponding linked list, calculate the sum with the carry carry, and then update the value of the carry. Then we add the current bit to the answer linked list. If both linked lists are traversed, and the carry is 0, the traversal ends.

Finally, we return the head node of the answer linked list.

The time complexity is O(max (m, n)), where m and n are the lengths of the two linked lists. We need to traverse the entire position of the two linked lists, and each position only needs O(1) time. Ignoring the space consumption of the answer, the space complexity is O(1).

Code

PythonJavaC++GoTypeScriptRustJavaScriptC#PHPSwiftRubyNimC

Python

Java

C++

Go

TypeScript

Rust

JavaScript

C#

PHP

Swift

Ruby

Nim

C

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Iterative Approach

Time Complexity: O(max(m, n)) where m and n are the lengths of the input lists. This is because we iterate through each node exactly once.
Space Complexity: O(max(m, n)) to store the resulting list.

Recursive Approach

Time Complexity: O(max(m, n))
Space Complexity: O(max(m, n)) because of the recursion stack.

Simulation—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Iterative Linked List AdditionO(max(m,n))O(1) extraStandard interview solution; best when you want minimal memory overhead
Recursive Digit AdditionO(max(m,n))O(n)Useful when recursion is preferred for cleaner code or conceptual clarity

Video Solution

Add Two Numbers - Leetcode 2 - Python • NeetCode • 371,715 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Add Two Numbers easy or hard?
Add Two Numbers is generally classified as a Medium difficulty problem. The main challenge is correctly handling different list lengths and carry propagation while constructing the result linked list.
Add Two Numbers Python/Java solution
In Python or Java, the solution typically uses a loop that iterates through both linked lists while tracking a carry variable. A dummy head node is used to simplify result construction, and new nodes are appended as each digit of the sum is calculated.
How to solve Add Two Numbers in O(n)?
Traverse both linked lists simultaneously and maintain a carry variable. At each step compute sum = digit1 + digit2 + carry, store sum % 10 as the new node, and update carry = sum // 10. Continue until both lists are exhausted and no carry remains, giving an O(n) solution where n is the longer list length.
What is the best approach for Add Two Numbers?
The standard solution uses iterative traversal of both linked lists while maintaining a carry value. Each step adds corresponding digits and stores the result digit in a new node. This approach runs in O(n) time and O(1) extra space, making it the most efficient and the most commonly expected answer in coding interviews.
Is Add Two Numbers asked at Google/Amazon/Meta?
Add Two Numbers is a classic linked list problem frequently reported in interviews at companies like Amazon, Google, Meta, and Microsoft. It tests pointer manipulation, carry handling, and understanding of linked list traversal.
What data structure is used in Add Two Numbers?
The core data structure is a singly linked list where each node stores a single digit. The algorithm traverses the lists node by node while constructing a new result linked list. Basic arithmetic operations are used to manage the carry between digits.
What is the time complexity of Add Two Numbers?
The time complexity is O(max(m,n)), where m and n are the lengths of the two linked lists. Each node from both lists is visited once to compute the digit sum and carry. Space complexity is O(1) for the iterative approach, excluding the output list.

Ready to solve this problem?

Practice Add Two Numbers with our built-in code editor and test cases.

Practice on FleetCode
Previous

Add Binary

Next

Add Strings