Start learning free

LESSON 151 OF 321 · LINKED LISTS

Add Two Numbers in C++ (Time Complexity: O(max(n, m)))

Practice O(n) Read the full explanation

You get two linked lists, list1 and list2. Each one holds a whole number (0 or more), one digit per node.

The digits are stored starting with the ones digit. For example, 472 is the list 2 -> 7 -> 4.

Return the sum of the two numbers as a new list, stored the same way.

Neither number has extra zeros in front. So a list ends in 0 only when it is just [0].

Example 1:

Input: list1 = [5,8,1], list2 = [7,3]
Output: [2,2,2]
Explanation: The numbers are 185 and 37.
185 + 37 = 222.
Ones: 5 + 7 = 12. Write 2 and carry 1.
Tens: 8 + 3 + 1 = 12. Write 2 and carry 1.
Hundreds: 1 + 1 = 2.

list1 list2 sum 5 8 1 7 3 2 2 2

Example 2:

Input: list1 = [9,9], list2 = [1]
Output: [0,0,1]
Explanation: 99 + 1 = 100.
The last carry needs a node of its own.

Example 3:

Input: list1 = [0], list2 = [4,3]
Output: [4,3]
Explanation: 0 + 34 = 34.

Constraints:

  • Each list has 1 to 100 nodes.
  • Each node holds one digit, from 0 to 9.

STEP 1 OF 12
    Ctrl + Enter to check

    C++ · LINKED LISTS

    Add Two Numbers in C++, explained

    Understanding the Problem

    The core challenge of this problem is to handle the addition of two numbers represented as linked lists, where each node contains a single digit. The digits are stored in reverse order, which means the least significant digit comes first. This is similar to how we perform addition manually, starting from the rightmost digit and moving to the left.

    Common applications of this problem include scenarios where large numbers need to be processed that cannot fit into standard data types, such as in financial calculations or scientific computations.

    Potential pitfalls include handling the carry-over correctly and ensuring that the resulting linked list is properly constructed without any leading zeros (except for the number 0 itself).

    Approach

    To solve this problem, we can use a straightforward approach that mimics the manual addition process:

    1. Initialize a dummy node to act as the head of the result linked list.
    2. Use two pointers to traverse the input linked lists.
    3. Initialize a carry variable to handle the carry-over during addition.
    4. Iterate through the linked lists, adding corresponding digits along with the carry.
    5. Create new nodes for the result linked list and update the carry accordingly.
    6. Handle any remaining carry after the main loop.

    This approach ensures that we correctly handle the addition of digits and the carry-over, resulting in the correct sum represented as a linked list.

    Algorithm

    Here is a step-by-step breakdown of the algorithm:

    1. Initialize a dummy node and a current pointer to build the result linked list.
    2. Initialize a carry variable to 0.
    3. While either of the input linked lists has nodes left or there is a carry:
      • Get the values of the current nodes of the input linked lists (or 0 if the list is exhausted).
      • Calculate the sum of the values and the carry.
      • Update the carry to be the sum divided by 10.
      • Create a new node with the value of the sum modulo 10 and attach it to the result linked list.
      • Move the current pointers of the input linked lists and the result linked list to the next nodes.
    4. Return the next node of the dummy node as the head of the result linked list.

    Code Implementation

    
    #include <iostream>
    using namespace std;
    
    // Definition for singly-linked list.
    struct ListNode {
        int val;
        ListNode *next;
        ListNode() : val(0), next(nullptr) {}
        ListNode(int x) : val(x), next(nullptr) {}
        ListNode(int x, ListNode *next) : val(x), next(next) {}
    };
    
    class Solution {
    public:
        ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
            // Initialize a dummy node to act as the head of the result linked list
            ListNode* dummy = new ListNode();
            ListNode* current = dummy;
            int carry = 0;
    
            // Traverse both linked lists
            while (l1 != nullptr || l2 != nullptr || carry != 0) {
                // Get the values of the current nodes (or 0 if the list is exhausted)
                int val1 = (l1 != nullptr) ? l1->val : 0;
                int val2 = (l2 != nullptr) ? l2->val : 0;
    
                // Calculate the sum and update the carry
                int sum = val1 + val2 + carry;
                carry = sum / 10;
    
                // Create a new node with the value of sum % 10
                current->next = new ListNode(sum % 10);
                current = current->next;
    
                // Move to the next nodes
                if (l1 != nullptr) l1 = l1->next;
                if (l2 != nullptr) l2 = l2->next;
            }
    
            // Return the next node of the dummy node as the head of the result linked list
            return dummy->next;
        }
    };
    
    // Helper function to print the linked list
    void printList(ListNode* node) {
        while (node != nullptr) {
            cout << node->val << " ";
            node = node->next;
        }
        cout << endl;
    }
    
    // Main function to test the solution
    int main() {
        // Create the first linked list: 2 -> 4 -> 3
        ListNode* l1 = new ListNode(2);
        l1->next = new ListNode(4);
        l1->next->next = new ListNode(3);
    
        // Create the second linked list: 5 -> 6 -> 4
        ListNode* l2 = new ListNode(5);
        l2->next = new ListNode(6);
        l2->next->next = new ListNode(4);
    
        // Create a solution object
        Solution solution;
    
        // Add the two numbers
        ListNode* result = solution.addTwoNumbers(l1, l2);
    
        // Print the result linked list
        printList(result);
    
        return 0;
    }
    

    Complexity Analysis

    The time complexity of this approach is O(max(n, m)), where n and m are the lengths of the input linked lists. This is because we traverse both linked lists once. The space complexity is O(max(n, m)) as well, due to the space required for the result linked list.

    Edge Cases

    Potential edge cases include:

    • One or both input linked lists are empty.
    • The input linked lists have different lengths.
    • The sum results in an additional carry at the end.

    Our algorithm handles these edge cases by checking for null pointers and ensuring the carry is correctly managed.

    Testing

    To test the solution comprehensively, we can use a variety of test cases:

    • Simple cases with small numbers.
    • Cases with different lengths of input linked lists.
    • Cases where the sum results in an additional carry.

    We can use the provided helper function to print the linked list and verify the results manually.

    Thinking and Problem-Solving Tips

    When approaching such problems, it is essential to:

    • Break down the problem into smaller, manageable parts.
    • Think about how you would solve the problem manually and translate that into code.
    • Consider edge cases and how to handle them.
    • Write clean, readable code with comments to explain your thought process.

    Practicing similar problems and studying algorithms can help improve problem-solving skills.

    Conclusion

    In this blog post, we discussed how to solve the problem of adding two numbers represented as linked lists. We covered the problem definition, approach, algorithm, code implementation, complexity analysis, edge cases, and testing. Understanding and solving such problems is crucial for developing strong problem-solving skills and improving coding proficiency.

    We encourage readers to practice and explore further to enhance their understanding and skills.

    Additional Resources

    For further reading and practice, consider the following resources:

    Keep going with C++1,600+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free