Add Two Numbers II solution and explanation
Google
9 more videos on this problem
Add Two Numbers II | Follow Up Qn Also | 2 Approaches | AMAZON | MICROSOFT | Leetcode-445codestorywithMIK · 28:30 · 16K views
Add Two Numbers II | LeetCode 445 | Add Two Numbers Represented by Linked ListsProgramming Tutorials · 10:35 · 3K views
Add Two Numbers II | Leet code 445 | Theory explained + Python codeSai Anish Malla · 14:04 · 3K views
Leetcode 445 Add Two Numbers IIJeevan Kumar - Cracckify · 5:16 · 1K views
Add Two numbers II | LeetCode 445 | MediumCode And Coffee · 27:49 · 1K views
Add Two Numbers II - Leetcode 445 - PythonTechError · 7:23 · 1K views
445. Add Two Numbers II 两数相加 II【LeetCode 力扣题解】LeetCode 力扣 · 3:27 · 1K views
Add two numbers II Leetcode | Leetcode 445 | Leetcode november challengeCode Bashers · 12:56 · 1K views
Daily Leetcode #1203: Jul 17, 2023 - 445. Add Two Numbers IIProgramming Live with Larry · 17:40 · 310 views
Add Two Numbers II - Leetcode 445 - C++ SolutionGyan Portal · 6:01 · 243 views
The problem
You are given two non-empty linked lists representing two non-negative integers. The most significant digit comes first 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 = [7,2,4,3], l2 = [5,6,4] Output: [7,8,0,7]
Example 2:
Input: l1 = [2,4,3], l2 = [5,6,4] Output: [8,0,7]
Example 3:
Input: l1 = [0], l2 = [0] Output: [0]
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.
Follow up: Could you solve it without reversing the input lists?
Approach overview
Problem Overview: Two non-empty linked lists represent two non‑negative integers. Each node stores a single digit and the most significant digit appears first. Add the numbers and return the result as a linked list in the same forward order.
The challenge comes from the forward ordering. Addition normally starts from the least significant digit, but a singly linked list gives access from the head only. You must either reverse the traversal order or simulate it with another structure.
Approach 1: Reversal of Linked Lists (Time: O(n), Space: O(1))
Reverse both input lists so the least significant digits appear first. After reversal, the problem becomes identical to the classic Add Two Numbers problem. Traverse both reversed lists, compute sum = digit1 + digit2 + carry, create nodes for sum % 10, and propagate the carry. Finally reverse the resulting list again to restore forward order.
This approach modifies the original lists but avoids extra auxiliary structures. The key operations are pointer reversal and standard digit-by-digit addition. It works well when in-place modification is allowed and you want constant auxiliary space. The algorithm mainly relies on pointer manipulation typical in linked list problems.
Approach 2: Stack Data Structure (Time: O(n), Space: O(n))
Push all digits from each linked list into two stacks. This reverses the processing order because stacks pop the most recently inserted element first. After both stacks are filled, repeatedly pop digits, compute the current sum with carry, and create nodes at the front of the result list.
The trick is inserting new nodes at the head of the result list so the final order remains forward. Each iteration performs constant work: two stack pops, a carry calculation, and a node insertion. This method preserves the original lists and cleanly simulates reverse traversal. The technique combines stack behavior with digit addition logic from math problems.
Recommended for interviews: The stack approach is typically expected because the problem explicitly avoids modifying input lists. It demonstrates understanding of order reversal using auxiliary data structures. The reversal approach is still valuable to discuss—it shows you recognize the reduction to the classic addition problem and understand linked list manipulation.
Approach 1: Using Reversal of Linked Lists
This approach involves reversing both linked lists to align the least significant digits and performing the addition operation similarly to how you would add numbers on paper. After the sum is calculated, the result is reversed to restore the original order.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
def reverseList(self, head):
prev = None
current = head
while current:
next_temp = current.next
current.next = prev
prev = current
current = next_temp
return prev
def addTwoNumbers(self, l1, l2):
l1 = self.reverseList(l1)
l2 = self.reverseList(l2)
carry = 0
dummy = ListNode(0)
current = dummy
while l1 or l2 or carry != 0:
total = carry
if l1:
total += l1.val
l1 = l1.next
if l2:
total += l2.val
l2 = l2.next
carry = total // 10
current.next = ListNode(total % 10)
current = current.next
return self.reverseList(dummy.next)class ListNode {
int val;
ListNode next;
ListNode(int x) { val = x; }
}
public class Solution {
private ListNode reverse(ListNode head) {
ListNode prev = null;
while (head != null) {
ListNode nextTemp = head.next;
head.next = prev;
prev = head;
head = nextTemp;
}
return prev;
}
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
l1 = reverse(l1);
l2 = reverse(l2);
ListNode dummy = new ListNode(0);
ListNode current = dummy;
int carry = 0;
while (l1 != null || l2 != null || carry != 0) {
int sum = carry;
if (l1 != null) {
sum += l1.val;
l1 = l1.next;
}
if (l2 != null) {
sum += l2.val;
l2 = l2.next;
}
carry = sum / 10;
current.next = new ListNode(sum % 10);
current = current.next;
}
return reverse(dummy.next);
}
}#include <iostream>
#include <stack>
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
ListNode* reverseList(ListNode* head) {
ListNode* prev = NULL;
while (head) {
ListNode* nextTemp = head->next;
head->next = prev;
prev = head;
head = nextTemp;
}
return prev;
}
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
l1 = reverseList(l1);
l2 = reverseList(l2);
ListNode* dummy = new ListNode(0);
ListNode* current = dummy;
int carry = 0;
while (l1 || l2 || carry) {
int sum = carry;
if (l1) {
sum += l1->val;
l1 = l1->next;
}
if (l2) {
sum += l2->val;
l2 = l2->next;
}
carry = sum / 10;
current->next = new ListNode(sum % 10);
current = current->next;
}
return reverseList(dummy->next);
}class ListNode {
constructor(val = 0, next = null) {
this.val = val;
this.next = next;
}
}
function reverseList(head) {
let prev = null;
while (head !== null) {
let nextTemp = head.next;
head.next = prev;
prev = head;
head = nextTemp;
}
return prev;
}
function addTwoNumbers(l1, l2) {
l1 = reverseList(l1);
l2 = reverseList(l2);
let dummy = new ListNode(0);
let current = dummy;
let carry = 0;
while (l1 !== null || l2 !== null || carry !== 0) {
let sum = carry;
if (l1 !== null) {
sum += l1.val;
l1 = l1.next;
}
if (l2 !== null) {
sum += l2.val;
l2 = l2.next;
}
carry = Math.floor(sum / 10);
current.next = new ListNode(sum % 10);
current = current.next;
}
return reverseList(dummy.next);
}#include <stdio.h>
#include <stdlib.h>
struct ListNode {
int val;
struct ListNode *next;
};
struct ListNode* reverseList(struct ListNode* head) {
struct ListNode* prev = NULL;
struct ListNode* current = head;
while (current != NULL) {
struct ListNode* nextTemp = current->next;
current->next = prev;
prev = current;
current = nextTemp;
}
return prev;
}
struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2) {
l1 = reverseList(l1);
l2 = reverseList(l2);
struct ListNode dummy;
dummy.next = NULL;
struct ListNode* current = &dummy;
int carry = 0;
while (l1 != NULL || l2 != NULL || carry) {
int sum = carry;
if (l1 != NULL) {
sum += l1->val;
l1 = l1->next;
}
if (l2 != NULL) {
sum += l2->val;
l2 = l2->next;
}
carry = sum / 10;
struct ListNode* newNode = malloc(sizeof(struct ListNode));
newNode->val = sum % 10;
newNode->next = current->next;
current->next = newNode;
}
return reverseList(dummy.next);
}public class ListNode {
public int val;
public ListNode next;
public ListNode(int value) { val = value; }
}
public class Solution {
private ListNode Reverse(ListNode head) {
ListNode prev = null;
while (head != null) {
ListNode nextTemp = head.next;
head.next = prev;
prev = head;
head = nextTemp;
}
return prev;
}
public ListNode AddTwoNumbers(ListNode l1, ListNode l2) {
l1 = Reverse(l1);
l2 = Reverse(l2);
ListNode dummy = new ListNode(0);
ListNode current = dummy;
int carry = 0;
while (l1 != null || l2 != null || carry != 0) {
int sum = carry;
if (l1 != null) {
sum += l1.val;
l1 = l1.next;
}
if (l2 != null) {
sum += l2.val;
l2 = l2.next;
}
carry = sum / 10;
current.next = new ListNode(sum % 10);
current = current.next;
}
return Reverse(dummy.next);
}
}In Python, after reversing the input lists, this code calculates the sum of corresponding nodes, accounts for any carry, and prepends nodes to build the result list, which is also reversed at completion.
Time Complexity: O(n + m) where n and m are list lengths. Space Complexity: O(1), excluding the output list space.
Approach 2: Using Stack Data Structure
Another efficient way to solve this problem is using stacks to store digits of both the numbers. This helps to access the least significant digits last, similar to reversing. This allows easier management of carry as we traverse backward effectively without modifying input lists explicitly.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
def addTwoNumbers(self, l1, l2):
stack1, stack2 = [], []
while l1:
stack1.append(l1.val)
l1 = l1.next
while l2:
stack2.append(l2.val)
l2 = l2.next
carry = 0
result = None
while stack1 or stack2 or carry:
total = carry
if stack1: total += stack1.pop()
if stack2: total += stack2.pop()
carry = total // 10
newNode = ListNode(total % 10)
newNode.next = result
result = newNode
return resultimport java.util.Stack;
class ListNode {
int val;
ListNode next;
ListNode(int x) { val = x; }
}
public class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
Stack<Integer> stack1 = new Stack<>();
Stack<Integer> stack2 = new Stack<>();
while (l1 != null) {
stack1.push(l1.val);
l1 = l1.next;
}
while (l2 != null) {
stack2.push(l2.val);
l2 = l2.next;
}
int carry = 0;
ListNode result = null;
while (!stack1.isEmpty() || !stack2.isEmpty() || carry != 0) {
int sum = carry;
if (!stack1.isEmpty()) sum += stack1.pop();
if (!stack2.isEmpty()) sum += stack2.pop();
carry = sum / 10;
ListNode newNode = new ListNode(sum % 10);
newNode.next = result;
result = newNode;
}
return result;
}
}#include <iostream>
#include <stack>
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
std::stack<int> s1, s2;
while (l1) {
s1.push(l1->val);
l1 = l1->next;
}
while (l2) {
s2.push(l2->val);
l2 = l2->next;
}
int carry = 0;
ListNode* result = NULL;
while (!s1.empty() || !s2.empty() || carry) {
int sum = carry;
if (!s1.empty()) {
sum += s1.top();
s1.pop();
}
if (!s2.empty()) {
sum += s2.top();
s2.pop();
}
carry = sum / 10;
ListNode* newNode = new ListNode(sum % 10);
newNode->next = result;
result = newNode;
}
return result;
}class ListNode {
constructor(val = 0, next = null) {
this.val = val;
this.next = next;
}
}
function addTwoNumbers(l1, l2) {
let stack1 = [], stack2 = [];
while (l1) {
stack1.push(l1.val);
l1 = l1.next;
}
while (l2) {
stack2.push(l2.val);
l2 = l2.next;
}
let carry = 0;
let result = null;
while (stack1.length > 0 || stack2.length > 0 || carry !== 0) {
let sum = carry;
if (stack1.length > 0) sum += stack1.pop();
if (stack2.length > 0) sum += stack2.pop();
carry = Math.floor(sum / 10);
let newNode = new ListNode(sum % 10);
newNode.next = result;
result = newNode;
}
return result;
}#include <stdio.h>
#include <stdlib.h>
struct ListNode {
int val;
struct ListNode *next;
};
struct Stack {
int* array;
int top;
int capacity;
};
struct Stack* createStack(int capacity) {
struct Stack* stack = (struct Stack*)malloc(sizeof(struct Stack));
stack->capacity = capacity;
stack->top = -1;
stack->array = (int*)malloc(stack->capacity * sizeof(int));
return stack;
}
int isFull(struct Stack* stack) { return stack->top == stack->capacity - 1; }
int isEmpty(struct Stack* stack) { return stack->top == -1; }
void push(struct Stack* stack, int item) {
stack->array[++stack->top] = item;
}
int pop(struct Stack* stack) {
return stack->array[stack->top--];
}
struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2) {
struct Stack* s1 = createStack(100);
struct Stack* s2 = createStack(100);
struct ListNode* current = l1;
while (current) {
push(s1, current->val);
current = current->next;
}
current = l2;
while (current) {
push(s2, current->val);
current = current->next;
}
int carry = 0;
struct ListNode* result = NULL;
while (!isEmpty(s1) || !isEmpty(s2) || carry) {
int sum = carry;
if (!isEmpty(s1)) sum += pop(s1);
if (!isEmpty(s2)) sum += pop(s2);
carry = sum / 10;
struct ListNode* newNode = (struct ListNode*)malloc(sizeof(struct ListNode));
newNode->val = sum % 10;
newNode->next = result;
result = newNode;
}
return result;
}using System.Collections.Generic;
public class ListNode {
public int val;
public ListNode next;
public ListNode(int val = 0, ListNode next = null) {
this.val = val;
this.next = next;
}
}
public class Solution {
public ListNode AddTwoNumbers(ListNode l1, ListNode l2) {
Stack<int> stack1 = new Stack<int>();
Stack<int> stack2 = new Stack<int>();
while (l1 != null) {
stack1.Push(l1.val);
l1 = l1.next;
}
while (l2 != null) {
stack2.Push(l2.val);
l2 = l2.next;
}
int carry = 0;
ListNode result = null;
while (stack1.Count > 0 || stack2.Count > 0 || carry > 0) {
int sum = carry;
if (stack1.Count > 0) sum += stack1.Pop();
if (stack2.Count > 0) sum += stack2.Pop();
carry = sum / 10;
ListNode newNode = new ListNode(sum % 10);
newNode.next = result;
result = newNode;
}
return result;
}
}In Python, stacks are used for easy reverse-traversal of list digits, managing carry, and gradually forming the output linked list by prepending nodes from the sum operation.
Time Complexity: O(n + m), where n and m are the number of nodes in the lists respectively. Space Complexity: O(n + m) due to stack usage for digits.
Approach 3: Default Approach
/**
* Definition for singly-linked list.
* class ListNode {
* val: number
* next: ListNode | null
* constructor(val?: number, next?: ListNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
* }
*/
function addTwoNumbers(l1: ListNode | null, l2: ListNode | null): ListNode | null {
const s1: number[] = [];
const s2: number[] = [];
for (; l1; l1 = l1.next) {
s1.push(l1.val);
}
for (; l2; l2 = l2.next) {
s2.push(l2.val);
}
const dummy = new ListNode();
let carry = 0;
while (s1.length || s2.length || carry) {
const s = (s1.pop() ?? 0) + (s2.pop() ?? 0) + carry;
// const node = new ListNode(s % 10, dummy.next);
// dummy.next = node;
dummy.next = new ListNode(s % 10, dummy.next);
carry = Math.floor(s / 10);
}
return dummy.next;
}/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
s1, s2 := arraystack.New(), arraystack.New()
for l1 != nil {
s1.Push(l1.Val)
l1 = l1.Next
}
for l2 != nil {
s2.Push(l2.Val)
l2 = l2.Next
}
carry, dummy := 0, new(ListNode)
for !s1.Empty() || !s2.Empty() || carry > 0 {
s := carry
v, ok := s1.Pop()
if ok {
s += v.(int)
}
v, ok = s2.Pop()
if ok {
s += v.(int)
}
// node := &ListNode{s % 10, dummy.Next}
// dummy.Next = node
dummy.Next = &ListNode{s % 10, dummy.Next}
carry = s / 10
}
return dummy.Next
}// Definition for singly-linked list.
// #[derive(PartialEq, Eq, Clone, Debug)]
// pub struct ListNode {
// pub val: i32,
// pub next: Option<Box<ListNode>>
// }
//
// impl ListNode {
// #[inline]
// fn new(val: i32) -> Self {
// ListNode {
// next: None,
// val
// }
// }
// }
impl Solution {
fn reverse(mut head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
let mut pre = None;
while let Some(mut node) = head {
let next = node.next.take();
node.next = pre.take();
pre = Some(node);
head = next;
}
pre
}
pub fn add_two_numbers(
mut l1: Option<Box<ListNode>>,
mut l2: Option<Box<ListNode>>,
) -> Option<Box<ListNode>> {
l1 = Self::reverse(l1);
l2 = Self::reverse(l2);
let mut dummy = Some(Box::new(ListNode::new(0)));
let mut cur = &mut dummy;
let mut sum = 0;
while l1.is_some() || l2.is_some() || sum != 0 {
if let Some(node) = l1 {
sum += node.val;
l1 = node.next;
}
if let Some(node) = l2 {
sum += node.val;
l2 = node.next;
}
cur.as_mut().unwrap().next = Some(Box::new(ListNode::new(sum % 10)));
cur = &mut cur.as_mut().unwrap().next;
sum /= 10;
}
Self::reverse(dummy.unwrap().next.take())
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Using Reversal of Linked Lists | Time Complexity: O(n + m) where n and m are list lengths. Space Complexity: O(1), excluding the output list space. |
| Using Stack Data Structure | Time Complexity: O(n + m), where n and m are the number of nodes in the lists respectively. Space Complexity: O(n + m) due to stack usage for digits. |
| Default Approach | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Reversal of Linked Lists | O(n) | O(1) | When modifying the input lists is acceptable and you want constant auxiliary space |
| Stack Data Structure | O(n) | O(n) | Preferred when input lists must remain unchanged and reverse traversal is required |
Frequently asked questions
Is Add Two Numbers II easy or hard?
Add Two Numbers II is considered a medium difficulty problem. The arithmetic logic is straightforward, but handling forward-order linked lists requires an extra idea such as stacks or reversing the lists.
Add Two Numbers II Python/Java solution
Typical Python or Java solutions use either two stacks or linked list reversal. Both implementations iterate through digits, maintain a carry value, and construct the resulting linked list node by node in O(n) time.
How to solve Add Two Numbers II in O(n)?
Traverse each list once to either reverse it or push digits into stacks. Then process digits from least significant to most significant while maintaining a carry value. Each step performs constant work, so the entire algorithm finishes in O(n) time.
What is the best approach for Add Two Numbers II?
The stack-based approach is generally considered the best interview solution. Push digits from both linked lists into stacks, pop them to simulate reverse traversal, and build the result from the front while maintaining carry. This runs in O(n) time with O(n) extra space and keeps the original lists unchanged.
Is Add Two Numbers II asked at Google/Amazon/Meta?
Add Two Numbers II and its variant "Add Two Numbers" frequently appear in interviews at companies like Amazon, Google, Meta, and Microsoft. The problem tests linked list manipulation, stack usage, and handling carry during digit addition.
What data structure is used in Add Two Numbers II?
The primary data structures are singly linked lists and stacks. Linked lists store the digits in forward order, while stacks allow reverse processing of digits so addition can start from the least significant position.
What is the time complexity of Add Two Numbers II?
Both common approaches run in O(n) time where n is the number of nodes in the longer list. Each digit is processed once during addition. The stack method uses O(n) space while the linked list reversal approach can achieve O(1) auxiliary space.