Pseudo-code

text
function addTwoNumbers(l1, l2):
    num1 = convertListToNumber(l1)
    num2 = convertListToNumber(l2)
    sum = num1 + num2
    return convertNumberToList(sum)

Why this fails

While logically sound for small inputs, this approach fails due to integer overflow. The constraints state that the number of nodes in each linked list can be up to 100. A number with 100 digits far exceeds the capacity of standard 64-bit integers (like long in Java or long long in C++). Even if the language supports arbitrary-precision integers (like Python or Java's BigInteger), converting the entire list to a number requires $O(N)$ extra space and computation that ignores the structural advantage of the linked list format.

Core Insight for Add Two Numbers

The key intuition for the optimal solution is to simulate the elementary school method of column addition. When we add numbers manually on paper, we align them by the least significant digit (the ones place) and add them column by column, carrying over any value that exceeds 9 to the next column.

Conveniently, the problem provides the lists in reverse order. This means the head of l1 and the head of l2 are already aligned at the least significant digit. We do not need to reverse the lists or use stacks to access the end of the numbers; we can simply traverse from the head.

The primary invariant we must maintain is the carry. At any given position, the value of the new node is determined by: $\text{Sum} = \text{val1} + \text{val2} + \text{carry}$ $\text{New Node Value} = \text{Sum} \% 10$ $\text{New Carry} = \lfloor \text{Sum} / 10 \rfloor$

Visual Description: Imagine two pointers, one for each input list, moving rightward in lockstep. We also maintain a pointer for the result list. At each step, we pluck the values from the input pointers (treating null pointers as 0), add them to our current carry, and create a new node. The recursion or iteration "flows" from left to right, generating the output list directly. The process only terminates when both input lists are exhausted and the carry is zero.

Execution Flow

1. Initialize dummyHead to a new node (0).
2. Initialize current pointing to dummyHead.
3. Initialize carry to 0.
4. Begin loop while l1 != null OR l2 != null OR carry != 0:
   • Let x be l1.val if l1 exists, else 0.
   • Let y be l2.val if l2 exists, else 0.
   • Compute total = x + y + carry.
   • Update carry = total / 10 (integer division).
   • Create a new node with value total % 10.
   • Attach this new node to current.next.
   • Move current to current.next.
   • If l1 exists, move l1 to l1.next.
   • If l2 exists, move l2 to l2.next.
5. Return dummyHead.next.

Proof of Correctness

The algorithm guarantees correctness by strictly adhering to the mathematical definition of addition in base 10.

1. Base Case: The least significant digits are processed first (guaranteed by input format).
2. Inductive Step: For any position $i$, the digit is correctly computed as $(d1_i + d2_i + c_{i-1}) \pmod{10}$, and the carry $c_i$ is correctly propagated to position $i+1$.
3. Termination: The loop condition ensures processing continues until all input digits are consumed and no residual carry remains. This covers the edge case where the sum has more digits than the operands (e.g., $99 + 1 = 100$).

Reference Implementation

C++ Solution for LeetCode 2

cpp
/**
 * 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) {
        ListNode* dummyHead = new ListNode(0);
        ListNode* current = dummyHead;
        int carry = 0;

        // Iterate while there are nodes to process or a carry remains
        while (l1 != nullptr || l2 != nullptr || carry != 0) {
            int x = (l1 != nullptr) ? l1->val : 0;
            int y = (l2 != nullptr) ? l2->val : 0;
            
            int sum = x + y + carry;
            carry = sum / 10;
            
            current->next = new ListNode(sum % 10);
            current = current->next;
            
            if (l1 != nullptr) l1 = l1->next;
            if (l2 != nullptr) l2 = l2->next;
        }
        
        return dummyHead->next;
    }
};

Java Solution for LeetCode 2

java
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode dummyHead = new ListNode(0);
        ListNode current = dummyHead;
        int carry = 0;
        
        // Loop continues until both lists end and carry is resolved
        while (l1 != null || l2 != null || carry != 0) {
            int x = (l1 != null) ? l1.val : 0;
            int y = (l2 != null) ? l2.val : 0;
            
            int sum = x + y + carry;
            carry = sum / 10;
            
            current.next = new ListNode(sum % 10);
            current = current.next;
            
            if (l1 != null) l1 = l1.next;
            if (l2 != null) l2 = l2.next;
        }
        
        return dummyHead.next;
    }
}

Python Solution for LeetCode 2

python
# 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: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        dummy_head = ListNode(0)
        current = dummy_head
        carry = 0
        
        # Continue if either list has nodes or there is a carry
        while l1 is not None or l2 is not None or carry != 0:
            x = l1.val if l1 is not None else 0
            y = l2.val if l2 is not None else 0
            
            total = x + y + carry
            carry = total // 10
            
            current.next = ListNode(total % 10)
            current = current.next
            
            if l1 is not None:
                l1 = l1.next
            if l2 is not None:
                l2 = l2.next
                
        return dummy_head.next