algoadvance

Leetcode 445. Add Two Numbers II

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 not modify the input lists, and you have to return the result as a new linked list.

Example:

1. Input: l1 = [7,2,4,3], l2 = [5,6,4] Output: [7, 8, 0, 7]
2. Input: l1 = [2,4,3], l2 = [5,6,4] Output: [8, 0, 7]
3. Input: l1 = [0], l2 = [0] Output: [0]

Clarifying Questions:

1. Q: Can the input lists be of different lengths? A: Yes, the input linked lists can be of different lengths.

2. Q: Are the numbers always positive integers (excluding zero)? A: Yes, both numbers represented by the linked lists are non-negative integers.

3. Q: Should I handle cases where one or both lists are null? A: For the purpose of the problem, assume the lists are never null.

Strategy

1. Reverse the Input: To add numbers as humans do (from least significant digit to most significant digit), we need to reverse the linked lists.
2. Add Numbers: Once reversed, we can easily add the numbers digit by digit, handling the carry.
3. Reverse the Result: Since the final result must be presented with the most significant digit first, we will need to reverse the result linked list before returning it.

Code

#include <stack>

// 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) {
        std::stack<int> s1, s2;
        // Push the values of l1 into stack s1
        while (l1 != nullptr) {
            s1.push(l1->val);
            l1 = l1->next;
        }
        // Push the values of l2 into stack s2
        while (l2 != nullptr) {
            s2.push(l2->val);
            l2 = l2->next;
        }
        
        int carry = 0;
        ListNode* result = nullptr;
        // Adding numbers from least significant (top of the stacks) to most significant digit
        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();
            }
            // Make a new node for the current digit
            ListNode* node = new ListNode(sum % 10);
            node->next = result;
            result = node;
            carry = sum / 10;
        }
        
        return result;
    }
};

Time Complexity

• Time Complexity: O(n + m) where n is the length of the first linked list and m is the length of the second linked list. This complexity comes from iterating through each linked list to push elements onto the stack, then iterating through the stack to form the result list.

• Space Complexity: O(n + m) for storing the values in two stacks and for the new linked list.

This solution efficiently handles the problem without modifying the input lists and provides the result in the required format.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?