Problem Overview

The Add Two Numbers problem on LeetCode involves working with linked lists. You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each node contains a single digit.

You are asked to add the two numbers and return the sum as a linked list, also in reverse order.

You are given:

  • Two linked lists l1 and l2.
  • Each node contains a single digit (0–9), and the digits are stored in reverse order.

The goal is to simulate the addition of two numbers digit by digit, just like you would do by hand, and construct a new linked list representing the sum.

This problem is an excellent exercise for practicing linked list manipulation, carry handling, and implementing algorithms in multiple programming languages.

Problem Difficulty & Tags

On LeetCode, the Add Two Numbers problem is categorized as Medium. It’s not extremely difficult, but it requires careful handling of linked lists and the carry-over logic during addition.

From my perspective at Solviyo, this problem is a perfect example of how fundamental data structures like linked lists are used in real-world algorithmic challenges. Mastering this builds confidence for more complex problems.

Common tags associated with this problem:

  • Linked List
  • Math
  • Simulation

Understanding how to traverse multiple linked lists simultaneously while keeping track of carry is a key skill, and it’s often tested in coding interviews.

Understanding the Problem

At first glance, the Add Two Numbers problem might seem simple: just add two numbers represented by linked lists. But to implement it correctly, we need to understand the details carefully.

The numbers are stored in reverse order, which means:

  • The 1’s digit is at the head of the linked list.
  • The 10’s, 100’s, and higher digits follow sequentially.

For example, the linked list 2 → 4 → 3 represents the number 342. Similarly, 5 → 6 → 4 represents 465. Adding them gives 807, which should be returned as 7 → 0 → 8.

Key points to note:

  • We need to traverse both linked lists simultaneously.
  • We must handle carry-over properly for sums greater than 9.
  • We continue processing until both lists are exhausted and there is no remaining carry.
  • Finally, we return the new linked list representing the sum.

Understanding these rules is crucial, because a naive approach that ignores carry or mismanages node connections will fail.

Approach / Logic Explanation

To solve the Add Two Numbers problem efficiently, we need to simulate addition the way we do by hand, digit by digit, while managing carry-over. Here’s how I usually explain it at Solviyo.

Step 1: Initialize Pointers and Carry

We create a dummy node to simplify linked list construction and use a pointer to traverse the result list. We also initialize a carry variable to 0.

Step 2: Traverse Both Lists Simultaneously

While either l1 or l2 has nodes left, or carry is non-zero:

  • Sum the values of the current nodes from l1 and l2 along with the carry.
  • Compute the new digit as sum % 10 and update the carry as sum / 10 (or integer division in Python/Java).
  • Create a new node with the computed digit and attach it to the result list.
  • Move the pointers l1, l2, and the result pointer forward.

Step 3: Handle Remaining Carry

After processing both lists, if carry is still non-zero, we create an additional node for it. This ensures the final sum is correct even when the last addition produces an extra digit.

Step 4: Return the Result

Finally, we return the linked list starting from dummy.next, since dummy itself is just a placeholder.

This approach works for C++, Python, and Java. The key idea is careful management of pointers and carry, which allows us to add numbers of any length without converting them to integers.

Solution Code

Below are the implementations of the Add Two Numbers problem in C++, Python, and Java, using a dummy node and carry handling.

C++ Solution


class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode* dummy = new ListNode();
        ListNode* res = dummy;
        int total = 0, carry = 0;

        while (l1 || l2 || carry) {
            total = carry;

            if (l1) {
                total += l1->val;
                l1 = l1->next;
            }

            if (l2) {
                total += l2->val;
                l2 = l2->next;
            }

            int num = total % 10;
            carry = total / 10;
            dummy->next = new ListNode(num);
            dummy = dummy->next;
        }

        ListNode* result = res->next;
        delete res;
        return result;         
    }
};

Python Solution


class Solution:
    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        dummy = ListNode()
        res = dummy
        total = carry = 0

        while l1 or l2 or carry:
            total = carry

            if l1:
                total += l1.val
                l1 = l1.next

            if l2:
                total += l2.val
                l2 = l2.next

            num = total % 10
            carry = total // 10
            dummy.next = ListNode(num)
            dummy = dummy.next
        
        return res.next

Java Solution


class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode();
        ListNode res = dummy;
        int total = 0, carry = 0;

        while (l1 != null || l2 != null || carry != 0) {
            total = carry;

            if (l1 != null) {
                total += l1.val;
                l1 = l1.next;
            }

            if (l2 != null) {
                total += l2.val;
                l2 = l2.next;
            }

            int num = total % 10;
            carry = total / 10;
            dummy.next = new ListNode(num);
            dummy = dummy.next;
        }

        return res.next;        
    }
}

Step-by-Step Walkthrough

Let’s break down how your Add Two Numbers solution works in C++, Python, and Java, step by step.

Step 1: Initialize Dummy Node and Pointers

We start by creating a dummy node. This helps us easily build the result linked list without worrying about special cases for the head node. A pointer res keeps a reference to the head.

Step 2: Initialize Carry

We initialize carry to 0. This variable stores the carry-over value when the sum of two digits exceeds 9.

Step 3: Traverse the Linked Lists

We iterate while l1 or l2 has nodes remaining, or carry is not zero:

  • Add the current values of l1 and l2 to total along with carry.
  • Compute the digit for the new node as total % 10.
  • Update carry as total / 10 (or integer division in Python).
  • Create a new node with the calculated digit and attach it to the result list.
  • Move the l1, l2, and result pointers forward.

Step 4: Handle Remaining Carry

If there is still a non-zero carry after both lists are fully traversed, we create one additional node to store it. This ensures the final sum is correct.

Step 5: Return the Result

Finally, we return dummy.next as the head of the resulting linked list. The dummy node itself was just a placeholder to simplify list construction.

Key Observations

  • This approach works efficiently for lists of different lengths.
  • Carry is always correctly propagated across digits, just like manual addition.
  • Using a dummy node avoids extra conditional checks for the head of the result list.

Leetcode add two numbers

 

Sample Input & Output

Here are some examples to illustrate the input and expected output for the Add Two Numbers problem:

Input Output Explanation
l1 = [2 → 4 → 3]
l2 = [5 → 6 → 4]		 [7 → 0 → 8] Represents 342 + 465 = 807. The linked list is returned in reverse order.
l1 = [0]
l2 = [0]		 [0] 0 + 0 = 0. The result is a single node with value 0.
l1 = [9 → 9 → 9 → 9 → 9 → 9 → 9]
l2 = [9 → 9 → 9 → 9]		 [8 → 9 → 9 → 9 → 0 → 0 → 0 → 1] Handles carry across multiple nodes correctly, resulting in 10009998 in reverse order.

Time & Space Complexity Analysis

Let’s analyze the efficiency of the Add Two Numbers solution.

Time Complexity

  • We traverse both linked lists once, processing each node exactly once.
  • Let m be the length of l1 and n be the length of l2.
  • The total time complexity is O(max(m, n)), as we continue until both lists and any remaining carry are processed.

Space Complexity

  • We create a new linked list to store the result. In the worst case, the length of the result is max(m, n) + 1 due to possible carry-over.
  • No additional data structures are used apart from variables to store total and carry.
  • Therefore, space complexity is O(max(m, n)) for the output linked list.

Summary: The solution is efficient, traversing each node once and using only the necessary extra space for the output. This makes it suitable for large numbers represented as linked lists.

Mistakes to Avoid & Tips

Warning: Avoid converting linked lists to integers. For very large numbers, this will exceed integer limits and is inefficient.
Common Error: Forgetting to handle carry at the end. Always check if carry > 0 after processing both lists and add a new node if needed.
Pro Tip: Using a dummy node simplifies linked list construction and avoids special handling for the head node.
Note: Test edge cases such as lists of different lengths, lists containing zeros, or multiple carries across nodes to ensure correctness.

Related Problems

If you found the Add Two Numbers problem interesting, here are some similar linked list challenges to practice and strengthen your skills:

Conclusion

The Add Two Numbers problem is an excellent exercise for practicing linked list manipulation and handling carry-over logic. By simulating addition digit by digit, you can solve the problem efficiently without converting the linked lists to integers.

From my experience at Solviyo, mastering this problem builds a strong foundation for tackling more complex linked list problems, such as Add Two Numbers II or Merge Two Sorted Lists.

Key takeaways include understanding how to traverse multiple lists simultaneously, manage carry, and use a dummy node to simplify linked list construction. These patterns frequently appear in coding interviews.

Keep practicing, test edge cases, and focus on clean, readable code. Each problem you solve adds to your confidence and strengthens your problem-solving skills.