Add Two Numbers II

Problem Statement

In this problem, you are provided with two non-empty linked lists. Each linked list represents a non-negative integer where the most significant digit is at the head of the list. Every node in these linked lists contains a single digit. Your task is to add these two numbers represented by the linked lists and return the result as a new linked list in the same most significant digit first order.

Unlike typical numerical addition problems in arrays where values are stored from least significant to most significant, this problem stores the digits from most to least significant. This specific detail increases the complexity as one cannot simply start adding from the beginning of the lists.

Examples

Example 1

Input:

l1 = [7,2,4,3], l2 = [5,6,4]

Output:

[7,8,0,7]

Example 2

Input:

l1 = [2,4,3], l2 = [5,6,4]

Output:

[8,0,7]

Example 3

Input:

l1 = [0], l2 = [0]

Output:

[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.

Approach and Intuition

To approach this problem efficiently, we can break down the solution into more manageable steps based on the provided examples and constraints:

1. Reverse Both Lists: Since the linked lists have their digits stored from most to least significant, and typical addition requires accessing digits from least to most significant, you begin by reversing both linked lists. This alignment will allow for straightforward addition.

2. Add the Reversed Lists: Start from the head of these reversed lists and perform digit-by-digit addition, similar to how you might add numbers on paper. Remember to manage the carry that can result from adding two digits.

3. Create the Result List: As you compute the sums, construct a new linked list from the results. However, due to the initial reversal, this list will be in the reverse order (least significant digit first).

4. Reverse the Resultant List: Finally, reverse the resultant linked list so that it reflects the most significant digit first order, as required by the problem statement.

Further considerations based on constraints:

• Since each number is represented as a linked list with nodes ranging from 1 to 100 and digits between 0 and 9, the operations of reversing and summing are well within efficient computational limits.
• Care must be taken to handle a carry that might persist after the last digit has been processed (e.g., turning a 999 + 1 into 1000).

By leveraging list traversal and manipulation techniques, this approach ensures that we respect the order of digits and correctly perform the addition, resulting in a linked list that represents the sum of the input numbers.

Solutions

class Solution {
public:
    ListNode* sumTwoLinkedLists(ListNode* first, ListNode* second) {
        stack<int> digitsFirst, digitsSecond;
    
        while (first) {
            digitsFirst.push(first->val);
            first = first->next;
        }
    
        while (second) {
            digitsSecond.push(second->val);
            second = second->next;
        }
    
        int sum = 0, overflow = 0;
        ListNode* result = new ListNode();
        while (!digitsFirst.empty() || !digitsSecond.empty()) {
            if (!digitsFirst.empty()) {
                sum += digitsFirst.top();
                digitsFirst.pop();
            }
            if (!digitsSecond.empty()) {
                sum += digitsSecond.top();
                digitsSecond.pop();
            }
    
            result->val = sum % 10;
            overflow = sum / 10;
            ListNode* temp = new ListNode(overflow);
            temp->next = result;
            result = temp;
            sum = overflow;
        }
    
        return overflow == 0 ? result->next : result;
    }
};