Log inSign up
mediumLeetCodeNot Started

Add Two Numbers

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 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 · Standard Case (Lists of Equal Length):

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

Example 2 · Single Node Zeroes:

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

Example 3 · Different Lengths with Chained Carry:

Input: l1 = [9, 9, 9, 9, 9, 9, 9], l2 = [9, 9, 9, 9]
Output: [8, 9, 9, 9, 0, 0, 0, 1]
Explanation: 9999999 + 9999 = 10009998. The resulting list has length 8 due to carry overflow.

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:

  • Master the Sentinel Dummy Head pattern to eliminate null-checks during dynamic list construction.
  • Handle multi-stream parallel pointer traversal with unequal lengths.
  • Implement carry propagation and post-loop overflow handling correctly in linked data structures.

Pattern Recognition Trigger

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

Signals to Look For:

  • Problem involves arithmetic operations directly on linked lists.
  • Input is formatted in reverse order (head node represents units place 100).
  • Unequal list lengths with possible carry overflowing the final position.

Algorithmic Decision Tree:

  • Whenever building a new linked list from scratch, create a dummy node and advance a curr pointer.
  • While l1 != null || l2 != null || carry != 0, continue the loop to guarantee no trailing carry is lost.
  • If one list reaches null before the other, substitute 0 for its value instead of branching into multiple loops.

Connected Patterns:

Add Two Numbers II (Forward Order with Stacks)Add BinaryMultiply StringsMerge Two Sorted Lists

1. Brute Force — Array Extraction & BigInt Addition

Intuition

Extract all node values into big integers or digit arrays, perform arithmetic addition, and convert the resulting sum back into a singly linked list.

Algorithm

  1. Step 1: Traverse list l1, collecting digits into a string or BigInt.
  2. Step 2: Traverse list l2, collecting digits into a second string or BigInt.
  3. Step 3: Reverse both strings and compute sum = BigInt(str1) + BigInt(str2).
  4. Step 4: Convert the sum back to string, reverse it, and construct a new linked list node by node.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5
6using namespace std;
7
8struct ListNode {
9 int val;
10 ListNode* next;
11 ListNode(int x) : val(x), next(nullptr) {}
12};
13
14class Solution {
15public:
16 ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
17 vector<int> n1, n2;
18 while (l1) { n1.push_back(l1->val); l1 = l1->next; }
19 while (l2) { n2.push_back(l2->val); l2 = l2->next; }
20
21 vector<int> res;
22 int carry = 0, i = 0, j = 0;
23 while (i < n1.size() || j < n2.size() || carry) {
24 int sum = carry;
25 if (i < n1.size()) sum += n1[i++];
26 if (j < n2.size()) sum += n2[j++];
27 carry = sum / 10;
28 res.push_back(sum % 10);
29 }
30
31 ListNode dummy(0);
32 ListNode* curr = &dummy;
33 for (int v : res) {
34 curr->next = new ListNode(v);
35 curr = curr->next;
36 }
37 return dummy.next;
38 }
39};
40
41int main() {
42 ListNode* l1 = new ListNode(2);
43 l1->next = new ListNode(4);
44 l1->next->next = new ListNode(3);
45
46 ListNode* l2 = new ListNode(5);
47 l2->next = new ListNode(6);
48 l2->next->next = new ListNode(4);
49
50 Solution sol;
51 ListNode* res = sol.addTwoNumbers(l1, l2);
52
53 cout << "Brute Force Output: ";
54 while (res) {
55 cout << res->val << (res->next ? " -> " : "");
56 res = res->next;
57 }
58 cout << endl;
59 return 0;
60}

Time & Space Complexity

  • Time complexity: O(N + M) — Extracting digits into strings/arrays and parsing requires O(N + M) time.
  • Space complexity: O(N + M) — Intermediate strings or arrays store all N and M digits in memory.

Why Brute Force Doesn't Scale:

Converting linked lists to native numbers fails due to IEEE 754 floating point and 64-bit integer limits (overflows beyond 18 digits).

For two linked lists with 100,000 digits each, streaming digit-by-digit simulation processes addition in ~3ms with ~4MB RAM, whereas integer parsing crashes with integer overflow.

2. Better — Recursive Carry Simulation

Intuition

Solve the problem inductively: the head of the output list is (l1.val + l2.val + carry) % 10, and its next pointer points to the recursive sum of l1.next and l2.next with the new carry.

Algorithm

  1. Step 1: Base case: if l1 is null, l2 is null, and carry is 0, return null.
  2. Step 2: Compute sum = (l1 ? l1.val : 0) + (l2 ? l2.val : 0) + carry.
  3. Step 3: Create a new node res = new ListNode(sum % 10).
  4. Step 4: Set res.next = helper(l1 ? l1.next : null, l2 ? l2.next : null, sum / 10) and return res.
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 {
12public:
13 ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
14 return helper(l1, l2, 0);
15 }
16private:
17 ListNode* helper(ListNode* l1, ListNode* l2, int carry) {
18 if (!l1 && !l2 && carry == 0) return nullptr;
19 int sum = carry;
20 if (l1) sum += l1->val;
21 if (l2) sum += l2->val;
22
23 ListNode* node = new ListNode(sum % 10);
24 node->next = helper(l1 ? l1->next : nullptr, l2 ? l2->next : nullptr, sum / 10);
25 return node;
26 }
27};
28
29int main() {
30 ListNode* l1 = new ListNode(9);
31 ListNode* l2 = new ListNode(9);
32 Solution sol;
33 ListNode* res = sol.addTwoNumbers(l1, l2);
34
35 cout << "Recursive C++ Output: ";
36 while (res) {
37 cout << res->val << (res->next ? " -> " : "");
38 res = res->next;
39 }
40 cout << endl;
41 return 0;
42}

Time & Space Complexity

  • Time complexity: O(max(N, M)) — Makes one recursive call per digit in the longer input list.
  • Space complexity: O(max(N, M)) recursion stack — Recursive call stack reaches depth max(N, M) + 1.

3. Optimal — Single Pass Simulation with Dummy Head Sentinel

Intuition

Maintain a running carry and traverse both lists in parallel. Use a sentinel dummy head node to build the result list. Each iteration adds the available node values and the carry, creates one node with sum % 10, updates carry = sum / 10, and advances the pointers.

Algorithm

  1. Step 1: Initialize a dummy head: dummy = new ListNode(0) and a traversal pointer curr = dummy.
  2. Step 2: Initialize integer carry = 0.
  3. Step 3: Loop while l1 != null || l2 != null || carry != 0.
  4. Step 4: Extract val1 = l1 ? l1.val : 0 and val2 = l2 ? l2.val : 0.
  5. Step 5: Compute sum = val1 + val2 + carry, update carry = sum / 10.
  6. Step 6: Attach new node curr.next = new ListNode(sum % 10) and advance curr = curr.next.
  7. Step 7: Advance l1 and l2 if they are not null.
  8. Step 8: Return dummy.next.

Add Two Numbers Master Trace

2 of 2 questions left today
Step 1 / 3
Trace timeline33% explored
Current operationSTEP 1 OF 3
First node created with value 7
Visual state
Values and pointers at this exact step
linked list
l1 → 2l2 → 5carry → 0
Node 1
7
NULL
Check / comparison
2 + 5 + 0 = 7 < 10
Decision / next transition
Digit = 7, Carry = 0
Why this step matters

First node created with value 7.

Step 1 / 3
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 {
12public:
13 ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
14 ListNode dummy(0);
15 ListNode* curr = &dummy;
16 int carry = 0;
17
18 while (l1 != nullptr || l2 != nullptr || carry != 0) {
19 int val1 = (l1 != nullptr) ? l1->val : 0;
20 int val2 = (l2 != nullptr) ? l2->val : 0;
21 int sum = val1 + val2 + carry;
22
23 carry = sum / 10;
24 curr->next = new ListNode(sum % 10);
25 curr = curr->next;
26
27 if (l1 != nullptr) l1 = l1->next;
28 if (l2 != nullptr) l2 = l2->next;
29 }
30
31 return dummy.next;
32 }
33};
34
35int main() {
36 // Construct l1 = [2, 4, 3]
37 ListNode* l1 = new ListNode(2);
38 l1->next = new ListNode(4);
39 l1->next->next = new ListNode(3);
40
41 // Construct l2 = [5, 6, 4]
42 ListNode* l2 = new ListNode(5);
43 l2->next = new ListNode(6);
44 l2->next->next = new ListNode(4);
45
46 Solution sol;
47 ListNode* result = sol.addTwoNumbers(l1, l2);
48
49 cout << "Optimal Solution Result: ";
50 while (result != nullptr) {
51 cout << result->val << (result->next ? " -> " : "");
52 result = result->next;
53 }
54 cout << endl;
55
56 return 0;
57}

Time & Space Complexity

  • Time complexity: O(max(N, M)) — We iterate at most max(N, M) + 1 times, performing O(1) pointer operations and arithmetic per step.
  • Space complexity: O(1) auxiliary space (O(max(N, M)) for result list) — No auxiliary data structures or call stack frames are used. The returned linked list of length max(N, M) + 1 is required for output.

Approach Comparison Matrix

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

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Brute Force — Convert to Large IntegersO(N + M)O(N + M)Traverse l1 and l2 to construct native integer values, compute total sum, and reconstruct a linked list from the digits of the sum.Memory conversions and severe integer overflow limitations.
2.Better — Recursive Addition with CarryO(max(N, M))O(max(N, M)) recursion stackRecursively compute the sum of corresponding nodes, passing the carry to the next recursive invocation.Implicit call stack overhead.
3.Optimal — Single-Pass Iterative Simulation with Dummy HeadOptimalO(max(N, M))O(1) auxiliary spaceSimultaneously advance pointers through l1 and l2, tracking carry and constructing new result nodes in O(1) space per node.Optimal. Every digit must be read and output at least once.

Common Pitfalls & Crucial Edge Cases

Forgetting Trailing Carry

Ending the loop on while (l1 || l2) instead of while (l1 || l2 || carry). This drops the most significant carry digit in sums like 99 + 1 = 100.

Premature Null Dereferencing

Accessing l1.next without checking if (l1 != null). Always guard pointer progression.

Overcomplicating Unequal Lengths

Writing 3 separate while loops (one for both, one for remaining l1, one for remaining l2). A single unified loop with ternary val = node ? node.val : 0 is much cleaner and less error-prone.

Reversing Unnecessarily

Attempting to reverse the list when the problem already specifies reverse order storage.

Crucial Edge Cases to Validate:

  • Unequal List Lengths — One list (e.g. 7 nodes) is longer than the other (e.g. 3 nodes). Handled seamlessly by defaulting missing nodes to value 0.
  • Trailing Carry Overflow — Adding [9, 9] and [1] yields [0, 0, 1]. The carry != 0 condition in the while-loop ensures the final node with value 1 is created.
  • Single Zero Lists — [0] + [0] = [0]. Handled in the first iteration with no extra loops.
  • Repeated Chained Carries — [9, 9, 9] + [1] = [0, 0, 0, 1]. Carry propagates continuously across multiple nodes.

Interview Tips & Best Practices

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

  1. Immediately state the dummy head technique to the interviewer: 'I will use a sentinel dummy node to avoid edge-case handling for the head.'
  2. Point out that the problem statement gives numbers in reverse order (least significant digit first), which makes direct single-pass addition possible.
  3. Highlight the test case l1 = [9, 9], l2 = [1] early to demonstrate you are actively thinking about carry propagation beyond list boundaries.

Quick Comprehension Check

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

1.Why does the while loop condition check l1 != null || l2 != null || carry != 0 instead of just l1 != null && l2 != null?

2.What is the primary benefit of using a dummy sentinel node (dummy = new ListNode(0))?

3.What is the maximum space complexity of the optimal single-pass solution (excluding output)?

Back to DSA Sheet