Add Two Numbers II

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;
    }
};

This solution in C++ addresses the problem of adding two numbers represented by linked lists where each node contains a single digit. The digits are stored in reverse order, so the head of each list represents the least significant digit.

The process involves the following steps:

1. Initialize two stacks to store the digits of the two numbers. This will help process the digits in reverse order, which is necessary for proper addition from least to most significant digits.
2. Traverse through each linked list, pushing the value of each node onto the respective stack until reaching the end of the list.
3. Initialize variables to manage the sum result and overflow (carry) for digits that sum to 10 or more.
4. Create an empty result linked list to store the sum of the two numbers.
5. Loop through the stacks until both are empty:
   • Pop the top element from each stack (if not empty) and add them together along with any carry from the previous digit.
   • Determine the new digit by taking modulo 10 of the sum and handle the overflow by integer division of the sum by 10.
   • Prepend this new digit to the result linked list.
6. After processing all digits, if there is an overflow remaining, prepend this to the result.
7. Finally, the function returns the result linked list, skipping the initial dummy node if no overflow is present.

This method ensures efficient handling of the addition operation by leveraging stacks to reverse the input lists without altering their original structure, allowing for direct digit-by-digit addition and easy management of carries between digits.

public class Solution {
    public ListNode sumTwoNumbers(ListNode first, ListNode second) {
        Stack<Integer> stack1 = new Stack<Integer>();
        Stack<Integer> stack2 = new Stack<Integer>();
        
        while(first != null) {
            stack1.push(first.val);
            first = first.next;
        };
        while(second != null) {
            stack2.push(second.val);
            second = second.next;
        }
        
        int sum = 0, carryOver = 0;
        ListNode result = new ListNode();
        while (!stack1.empty() || !stack2.empty()) {
            if (!stack1.empty()) {
                sum += stack1.pop();
            }
            if (!stack2.empty()) {
                sum += stack2.pop();
            }
            
            result.val = sum % 10;
            carryOver = sum / 10;
            ListNode newHead = new ListNode(carryOver);
            newHead.next = result;
            result = newHead;
            sum = carryOver;
        }

        return carryOver == 0 ? result.next: result;
    }
}

The provided Java solution outlines a method for adding two linked lists that represent numbers. Here's a detailed overview of how the solution operates:

1. Define two stacks to help reverse the linked lists, as Java's Stack is used here to manage the individual digits.
2. Traverse through both linked lists, pushing each node's value onto the respective stacks until all nodes are processed.
3. Initialize variables for sum and carryOver to assist in computing the linked list representing the sum from least significant to most significant digits.
4. A while loop runs as long as either stack has elements. Within the loop:
   1. Pop values from both stacks if available, adding to the sum.
   2. Create a new linked list node with the value of the current digit, computed using the modulus operation on sum.
   3. Link the new node at the front of the result list, effectively reversing the order of digits to match the correct order of the number.
   4. Update the sum to be the carry value for the next iteration.
5. At the end, handle the condition where an extra carry might create a new leading digit.
6. Return the constructed linked list which holds the sum of the two numbers.

This method leverages stacks efficiently to handle operations on the linked list in a reversed order, simplifying the process of digit-by-digit addition and carry management. It ensures that the resultant linked list delivers the correct numerical addition of the two provided numbers, respecting linked list order constraints (most significant digit at the head of the list).

class Solution:
    def sumTwoLinkedLists(self, node1: Optional[ListNode], node2: Optional[ListNode]) -> Optional[ListNode]:
        stack1 = []
        stack2 = []

        while node1:
            stack1.append(node1.val)
            node1 = node1.next
        while node2:
            stack2.append(node2.val)
            node2 = node2.next

        sum_result = 0
        carry_over = 0
        result_node = ListNode()
        while stack1 or stack2:
            if stack1:
                sum_result += stack1.pop()
            if stack2:
                sum_result += stack2.pop()

            result_node.val = sum_result % 10
            carry_over = sum_result // 10
            current_head = ListNode(carry_over)
            current_head.next = result_node
            result_node = current_head
            sum_result = carry_over

        return result_node.next if carry_over == 0 else result_node

The provided solution in Python addresses the problem of adding two numbers represented by linked lists in reverse order. The central idea is to traverse each list from last digit to first (most significant to least significant) using stacks and construct the result as a new linked list.

• Initialize two empty stacks, stack1 and stack2, to store individual digits.
• Traverse each node of the input linked lists node1 and node2, pushing the value of each node onto respective stacks.
• Initialize sum_result as 0, to accumulate sum of the top elements of the stacks and any carry from the previous sum.
• Initialize a dummy node result_node to build the resulting linked list in correct order from least significant to most significant digit.
• Loop while there are elements in either stack.
  • For each non-empty stack, pop the top element and add it to sum_result.
  • Update the node value of result_node using modulo operation (sum_result % 10) to get the last digit.
  • Initialize carry_over using integer division (sum_result // 10 to handle carry-over digits.
  • Prepare for the next loop iteration by adjusting the linked list pointers and sum.
• Finally, return the next node of result_node if there was no leftover carry, otherwise return result_node.

This approach efficiently handles carry propagation when summing digits from least to most significant and builds the result linked list in the desired order without reversing the input lists.