Problem Description

Given two non-empty linked lists representing two non-negative integers, where the most significant digit comes first and each node contains a single digit, add the two numbers and return the sum as a linked list. The numbers do not contain any leading zero, except the number 0 itself.

• Each input linked list l1 and l2 represents a non-negative integer in forward order (most significant digit first).
• You may not modify the input lists (i.e., you cannot reverse them directly).
• Return the sum as a new linked list, also in forward order.
• There is exactly one valid solution for each input.

Thought Process

The main challenge is that the digits are stored in forward order, with the most significant digit at the head. This is the opposite of the classic "Add Two Numbers" problem, where digits are in reverse order (making addition easier). If we could reverse the lists, we could add from the least significant digit, carrying as needed. However, the problem restricts us from modifying the input lists.

A brute-force approach would be to convert the lists to numbers, add them, and then convert the result back to a linked list. However, this does not scale for very large numbers (beyond integer limits), and is not the intended solution.

Instead, we need to simulate the addition process starting from the least significant digit, which is at the end of the lists. Since we cannot traverse backwards in singly-linked lists, we need a way to process the nodes in reverse order without modifying the lists. This leads us to use auxiliary data structures like stacks to temporarily reverse the order.

Solution Approach

To solve the problem efficiently and within the given constraints, we use stacks to reverse the traversal order of the linked lists:

1. Traverse and Push to Stacks:
   • Iterate through each linked list and push each digit onto a stack (s1 for l1, s2 for l2).
   • This way, the top of each stack contains the least significant digit, enabling us to pop and add digits from right to left.
2. Add Digits with Carry:
   • Initialize a carry variable to 0 and a head pointer for the result list.
   • While either stack is non-empty or there is a carry:
   • Pop the top digit from each stack (use 0 if the stack is empty).
   • Add the digits and the carry.
   • Create a new node with the digit part of the sum (sum % 10).
   • Insert this node at the front of the result list (since we're adding from least to most significant).
   • Update the carry (carry = sum // 10).
3. Return Result:
   • When done, head points to the sum as a new linked list in forward order.

This approach avoids modifying the input and handles any number of digits, even those exceeding standard integer sizes.

Example Walkthrough

Input:
l1 = [7, 2, 4, 3] (represents 7243)
l2 = [5, 6, 4] (represents 564)

1. Push to stacks:
   • s1 = [7, 2, 4, 3] (top is 3)
   • s2 = [5, 6, 4] (top is 4)
2. First addition:
   • Pop 3 (from s1), 4 (from s2): 3 + 4 = 7, carry = 0
   • New node: 7
3. Second addition:
   • Pop 4 (from s1), 6 (from s2): 4 + 6 = 10, carry = 1
   • New node: 0 (insert before 7)
4. Third addition:
   • Pop 2 (from s1), 5 (from s2): 2 + 5 + 1 = 8, carry = 0
   • New node: 8 (insert before 0)
5. Fourth addition:
   • Pop 7 (from s1), 0 (s2 is empty): 7 + 0 = 7, carry = 0
   • New node: 7 (insert before 8)
6. Result:
   • Linked list: 7 → 8 → 0 → 7
   • Represents 7807 (7243 + 564)

Time and Space Complexity

Brute-force approach:

• Convert each list to an integer: O(n) time and space.
• Add the integers and convert back: O(n) time and space.
• But this fails for very large numbers (integer overflow).

• Time Complexity: O(m + n), where m and n are the lengths of the two lists. We traverse each list once and process each digit once.
• Space Complexity: O(m + n) for the stacks, plus O(max(m, n)) for the result list.
• This approach avoids integer overflow and handles arbitrarily large numbers.

Summary

The key insight is to process the digits from least significant to most significant, even though the input lists are in forward order. Using stacks allows us to reverse the traversal order without modifying the input. By carefully managing the carry and building the result list from the front, we efficiently solve the problem within the constraints. This approach is both elegant and robust, handling lists of different lengths and large numbers gracefully.

Code Implementation

# Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        s1, s2 = [], []
        while l1:
            s1.append(l1.val)
            l1 = l1.next
        while l2:
            s2.append(l2.val)
            l2 = l2.next

        carry = 0
        head = None
        while s1 or s2 or carry:
            x = s1.pop() if s1 else 0
            y = s2.pop() if s2 else 0
            total = x + y + carry
            node = ListNode(total % 10)
            node.next = head
            head = node
            carry = total // 10
        return head
      

// Definition for singly-linked list.
struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {}
};

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        std::stack<int> s1, s2;
        while (l1) {
            s1.push(l1->val);
            l1 = l1->next;
        }
        while (l2) {
            s2.push(l2->val);
            l2 = l2->next;
        }
        int carry = 0;
        ListNode* head = nullptr;
        while (!s1.empty() || !s2.empty() || carry) {
            int x = s1.empty() ? 0 : s1.top();
            if (!s1.empty()) s1.pop();
            int y = s2.empty() ? 0 : s2.top();
            if (!s2.empty()) s2.pop();
            int total = x + y + carry;
            ListNode* node = new ListNode(total % 10);
            node->next = head;
            head = node;
            carry = total / 10;
        }
        return head;
    }
};
      

// Definition for singly-linked list.
class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        java.util.Stack<Integer> s1 = new java.util.Stack<>();
        java.util.Stack<Integer> s2 = new java.util.Stack<>();
        while (l1 != null) {
            s1.push(l1.val);
            l1 = l1.next;
        }
        while (l2 != null) {
            s2.push(l2.val);
            l2 = l2.next;
        }
        int carry = 0;
        ListNode head = null;
        while (!s1.isEmpty() || !s2.isEmpty() || carry != 0) {
            int x = s1.isEmpty() ? 0 : s1.pop();
            int y = s2.isEmpty() ? 0 : s2.pop();
            int total = x + y + carry;
            ListNode node = new ListNode(total % 10);
            node.next = head;
            head = node;
            carry = total / 10;
        }
        return head;
    }
}
      

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
var addTwoNumbers = function(l1, l2) {
    const s1 = [], s2 = [];
    while (l1) {
        s1.push(l1.val);
        l1 = l1.next;
    }
    while (l2) {
        s2.push(l2.val);
        l2 = l2.next;
    }
    let carry = 0;
    let head = null;
    while (s1.length || s2.length || carry) {
        const x = s1.length ? s1.pop() : 0;
        const y = s2.length ? s2.pop() : 0;
        const total = x + y + carry;
        const node = new ListNode(total % 10);
        node.next = head;
        head = node;
        carry = Math.floor(total / 10);
    }
    return head;
};