Log inSign up
mediumLeetCodeNot Started

Add Two Numbers II

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Linked List
Solve on LeetCode
Lesson

Problem Statement

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.

Follow up: Could you solve it without reversing the input lists?

Example 1 · Standard Case:

Input: l1 = [7, 2, 4, 3], l2 = [5, 6, 4]
Output: [7, 8, 0, 7]
Explanation: 7243 + 564 = 7807.

Example 2 · Equal Single Digit Numbers with Carry:

Input: l1 = [5], l2 = [5]
Output: [1, 0]
Explanation: 5 + 5 = 10.

Example 3 · Single Zero Values:

Input: l1 = [0], l2 = [0]
Output: [0]
Explanation: 0 + 0 = 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 (except 0 itself).

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Handle forward-order linked list arithmetic without mutating original inputs.
  • Master Head Prepending (node.next = head; head = node;) for building forward lists.
  • Apply Stacks as an external traversal inversion mechanism.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Linked list represents numbers in forward order (MSB at head).
  • Constraint / Follow-up explicitly forbids mutating/reversing input lists.
  • Need LIFO (Last-In-First-Out) traversal on linked nodes.

Algorithmic Decision Tree:

  • Whenever you need reverse traversal without mutating the data structure, use a Stack.
  • To build a linked list in forward order without tail tracking, insert at head: newNode.next = head; head = newNode;.

Connected Patterns:

Add Two Numbers (Reverse Order)Daily Temperatures (Monotonic Stack)Evaluate Reverse Polish NotationPalindrome Linked List

1. Brute Force — In-Place Reversal & Forward Addition

Intuition

Reverse l1 and l2 to reduce the problem to Add Two Numbers I. Add them, and reverse the resulting list.

Algorithm

  1. Step 1: Write helper function to reverse a singly linked list.
  2. Step 2: Reverse l1 and l2 in-place.
  3. Step 3: Add the two reversed lists using elementary carry addition.
  4. Step 4: Reverse the result list and restore l1 and l2.
  5. Step 5: Return the reversed result head.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2
3using namespace std;
4
5struct ListNode {
6 int val;
7 ListNode* next;
8 ListNode(int x) : val(x), next(nullptr) {}
9};
10
11class Solution {
12private:
13 ListNode* reverseList(ListNode* head) {
14 ListNode* prev = nullptr;
15 ListNode* curr = head;
16 while (curr) {
17 ListNode* nxt = curr->next;
18 curr->next = prev;
19 prev = curr;
20 curr = nxt;
21 }
22 return prev;
23 }
24public:
25 ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
26 l1 = reverseList(l1);
27 l2 = reverseList(l2);
28
29 ListNode dummy(0);
30 ListNode* curr = &dummy;
31 int carry = 0;
32
33 while (l1 || l2 || carry) {
34 int sum = carry + (l1 ? l1->val : 0) + (l2 ? l2->val : 0);
35 carry = sum / 10;
36 curr->next = new ListNode(sum % 10);
37 curr = curr->next;
38 if (l1) l1 = l1->next;
39 if (l2) l2 = l2->next;
40 }
41
42 return reverseList(dummy.next);
43 }
44};
45
46int main() {
47 ListNode* l1 = new ListNode(7);
48 l1->next = new ListNode(2);
49 l1->next->next = new ListNode(4);
50 l1->next->next->next = new ListNode(3);
51
52 ListNode* l2 = new ListNode(5);
53 l2->next = new ListNode(6);
54 l2->next->next = new ListNode(4);
55
56 Solution sol;
57 ListNode* res = sol.addTwoNumbers(l1, l2);
58 cout << "Brute Force Output: ";
59 while (res) {
60 cout << res->val << (res->next ? " -> " : "");
61 res = res->next;
62 }
63 cout << endl;
64 return 0;
65}

Time & Space Complexity

  • Time complexity: O(N + M) — Reversing both lists takes O(N + M), adding takes O(max(N, M)), and final reversal takes O(max(N, M)).
  • Space complexity: O(1) auxiliary space — Mutates pointers in place without auxiliary data structures.

Why Brute Force Doesn't Scale:

Converting linked list numbers directly into standard 64-bit integer types fails beyond 18 digits.

For two 500-digit numbers, dual-stack simulation requires less than 50KB RAM and finishes in under 1ms.

2. Better — Recursive Length Padding

Intuition

Count lengths of both lists. Advance a pointer on the longer list until both tails are aligned, then recursively sum corresponding digits from right to left.

Algorithm

  1. Step 1: Calculate lengths len1 and len2.
  2. Step 2: Define recursive helper that sums aligned sublists and returns carry.
  3. Step 3: Recursively propagate carry back up the stack.
  4. Step 4: If carry remains after the head returns, prepend a new head with value carry.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2
3using namespace std;
4
5struct ListNode {
6 int val;
7 ListNode* next;
8 ListNode(int x) : val(x), next(nullptr) {}
9};
10
11class Solution {
12 int getLength(ListNode* node) {
13 int len = 0;
14 while (node) { len++; node = node->next; }
15 return len;
16 }
17
18 ListNode* addHelper(ListNode* l1, ListNode* l2, int diff, int& carry) {
19 if (!l1 && !l2) return nullptr;
20
21 ListNode* result = nullptr;
22 int sum = 0;
23 if (diff > 0) {
24 result = new ListNode(l1->val);
25 result->next = addHelper(l1->next, l2, diff - 1, carry);
26 sum = result->val + carry;
27 } else {
28 result = new ListNode(l1->val + l2->val);
29 result->next = addHelper(l1->next, l2->next, 0, carry);
30 sum = result->val + carry;
31 }
32
33 result->val = sum % 10;
34 carry = sum / 10;
35 return result;
36 }
37public:
38 ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
39 int len1 = getLength(l1), len2 = getLength(l2);
40 if (len1 < len2) { swap(l1, l2); swap(len1, len2); }
41
42 int carry = 0;
43 ListNode* head = addHelper(l1, l2, len1 - len2, carry);
44 if (carry) {
45 ListNode* newHead = new ListNode(carry);
46 newHead->next = head;
47 head = newHead;
48 }
49 return head;
50 }
51};
52
53int main() {
54 ListNode* l1 = new ListNode(7);
55 l1->next = new ListNode(2);
56 l1->next->next = new ListNode(4);
57 l1->next->next->next = new ListNode(3);
58
59 ListNode* l2 = new ListNode(5);
60 l2->next = new ListNode(6);
61 l2->next->next = new ListNode(4);
62
63 Solution sol;
64 ListNode* res = sol.addTwoNumbers(l1, l2);
65 cout << "Recursive C++ Output: ";
66 while (res) {
67 cout << res->val << (res->next ? " -> " : "");
68 res = res->next;
69 }
70 cout << endl;
71 return 0;
72}

Time & Space Complexity

  • Time complexity: O(N + M) — Computes lengths in O(N + M) and traverses both lists recursively in O(max(N, M)).
  • Space complexity: O(max(N, M)) recursion stack — Recursion call stack depth equals max(N, M).

3. Optimal — Dual Stack Inversion with Head Prepending

Intuition

By pushing the linked lists into two stacks, the top of each stack becomes the least significant digit. We pop from both stacks, sum with carry, and prepend each new digit to the head of the output list (newNode.next = head; head = newNode;).

Algorithm

  1. Step 1: Push all node values from l1 onto stack s1.
  2. Step 2: Push all node values from l2 onto stack s2.
  3. Step 3: Initialize head = null and carry = 0.
  4. Step 4: While s1 is not empty, s2 is not empty, or carry != 0:
  5. Step 5: Pop v1 = s1.pop() (or 0 if empty) and v2 = s2.pop() (or 0 if empty).
  6. Step 6: Compute sum = v1 + v2 + carry and update carry = sum / 10.
  7. Step 7: Create node = new ListNode(sum % 10) and prepend to head: node.next = head; head = node;.
  8. Step 8: Return head.

Add Two Numbers II Master Trace

2 of 2 questions left today
Step 1 / 4
Trace timeline25% explored
Current operationSTEP 1 OF 4
List: [7]
Visual state
Values and pointers at this exact step
linked list
head → 7
Node 1
7
NULL
Check / comparison
3 + 4 = 7
Decision / next transition
Prepend 7 to head
Why this step matters

List: [7]

Step 1 / 4
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <stack>
3
4using namespace std;
5
6struct ListNode {
7 int val;
8 ListNode* next;
9 ListNode(int x) : val(x), next(nullptr) {}
10};
11
12class Solution {
13public:
14 ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
15 stack<int> s1, s2;
16 while (l1) { s1.push(l1->val); l1 = l1->next; }
17 while (l2) { s2.push(l2->val); l2 = l2->next; }
18
19 ListNode* head = nullptr;
20 int carry = 0;
21
22 while (!s1.empty() || !s2.empty() || carry) {
23 int sum = carry;
24 if (!s1.empty()) { sum += s1.top(); s1.pop(); }
25 if (!s2.empty()) { sum += s2.top(); s2.pop(); }
26
27 carry = sum / 10;
28 ListNode* node = new ListNode(sum % 10);
29 node->next = head;
30 head = node;
31 }
32
33 return head;
34 }
35};
36
37int main() {
38 ListNode* l1 = new ListNode(7);
39 l1->next = new ListNode(2);
40 l1->next->next = new ListNode(4);
41 l1->next->next->next = new ListNode(3);
42
43 ListNode* l2 = new ListNode(5);
44 l2->next = new ListNode(6);
45 l2->next->next = new ListNode(4);
46
47 Solution sol;
48 ListNode* result = sol.addTwoNumbers(l1, l2);
49
50 cout << "Optimal Dual Stack Output: ";
51 while (result) {
52 cout << result->val << (result->next ? " -> " : "");
53 result = result->next;
54 }
55 cout << endl;
56 return 0;
57}

Time & Space Complexity

  • Time complexity: O(N + M) — Pushing all elements takes O(N + M) and popping to construct the list takes O(max(N, M)).
  • Space complexity: O(N + M) — Two stacks store N and M values respectively.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Brute Force — Reverse Lists, Add, and Reverse BackO(N + M)O(1) auxiliary spaceMutate and reverse both input lists in-place, execute Add Two Numbers I, then reverse all lists back.Unsafe in-place mutation.
2.Better — Recursive Length AlignmentO(N + M)O(max(N, M)) recursion stackCount lengths, pad the shorter list with virtual zeros, recurse to the tail, and propagate carry backwards upon return.Call stack frames and code complexity.
3.Optimal — Dual Stack with Head PrependingOptimalO(N + M)O(N + M)Push all digits of l1 and l2 onto two stacks. Pop and add digit-by-digit, prepending nodes to the head of the output list.Optimal without mutating input lists.

Common Pitfalls & Crucial Edge Cases

Mutating the Input Lists

Reversing inputs when the interview follow-up explicitly forbids it.

Appending to Tail Instead of Prepending to Head

Using tail.next which requires another reversal. Prepending (node.next = head; head = node;) builds the list in correct forward order in O(1) time per node.

Integer Overflow with Conversions

Attempting to accumulate integers into long variables which overflow on 100-node lists.

Crucial Edge Cases to Validate:

  • Carrying into New Most Significant Digit — [5] + [5] = [1, 0]. The carry condition prepends node(1) at the very end.
  • Lists with Vastly Different Lengths — [9, 9, 9, 9] + [1] = [1, 0, 0, 0, 0]. Stacks handle different depths seamlessly.
  • Single Zeros — [0] + [0] = [0].
  • Chained Propagation across the entire number — [9, 9, 9] + [1] = [1, 0, 0, 0].

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. State immediately: 'Because the most significant digit is at the head and we cannot mutate the lists, I will use two stacks to achieve LIFO digit retrieval.'
  2. Explain the head prepending technique (node.next = head; head = node;) clearly to show you know how to build a linked list backwards in O(1) time.
  3. Verify the test case [5] + [5] = [1, 0] out loud to prove your loop handles the final carry.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why is the Dual Stack approach preferred over list reversal for the follow-up?

2.How does Head Prepending (node.next = head; head = node;) affect the final list order?

3.What happens if a carry remains after both stacks are empty (e.g. 99 + 1 = 100)?

Back to DSA Sheet