Add Two Numbers

LeetCode 2: Add Two Numbers Solution & Explanation

Problem Overview

TL;DR: Iterate through both linked lists simultaneously, summing values node-by-node while maintaining a "carry" variable to construct a new result list.

The LeetCode 2 problem, titled Add Two Numbers, asks us to perform arithmetic addition on two non-negative integers. However, these integers are not provided as standard primitives; they are represented as linked lists where the digits are stored in reverse order. This means the head of the list represents the ones place, the second node represents the tens place, and so on. We must return the sum as a new linked list in the same reverse-order format.

This is a classic interview question that tests your ability to handle pointer manipulation and basic arithmetic state management simultaneously.

Brute Force Approach for Add Two Numbers

A naive approach to solving this problem attempts to convert the linked list representations directly into standard integer types, perform the addition, and then convert the result back into a linked list.

Naive Algorithm

1. Traverse the first linked list (l1) to reconstruct the number it represents (e.g., 2 -> 4 -> 3 becomes 342).
2. Traverse the second linked list (l2) to reconstruct its number.
3. Calculate the sum of these two integers.
4. Convert the resulting sum back into a new linked list by extracting digits modulo 10.

Pseudo-code

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.

Algorithm Strategy: Linked List Manipulation Patterns

To implement this efficiently, we use the Dummy Head technique along with a single pass iteration.

1. Dummy Head: Create a placeholder node (dummy) to serve as the start of our result list. This simplifies edge cases where the result list is empty or we need to return the head easily.
2. Pointer Initialization: Initialize pointers for l1, l2, and a current pointer for the result list starting at the dummy.
3. Unified Loop: We iterate as long as there is data to process. The loop continues if l1 is not null, OR l2 is not null, OR carry is non-zero. This handles cases where lists are of different lengths or a final carry creates a new most significant digit (e.g., $500 + 500 = 1000$).
4. Value Extraction: Inside the loop, check if the current node for l1 or l2 is null. If it is, use 0 as the value; otherwise, use the node's value.
5. State Update: Calculate the sum, update the carry, create the new node, and advance the pointers.

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$).

Pattern Reuse Notes

The Linked List - Addition of Numbers pattern used here is directly applicable to several other interview problems. Mastering the logic of simultaneous traversal and carry management allows you to solve:

• LeetCode 369: Plus One Linked List - A variation where you add a single digit to a list (often requires reversing or recursion).
• LeetCode 445: Add Two Numbers II - The same problem but lists are in forward order. This requires using stacks or reversing the lists first to apply the exact same logic as LeetCode 2.
• LeetCode 67: Add Binary - While this uses strings, the "carry and traverse backwards" logic is identical to the linked list addition pattern.

Reference Implementation

C++ Solution for LeetCode 2

1/**
2 * Definition for singly-linked list.
3 * struct ListNode {
4 *     int val;
5 *     ListNode *next;
6 *     ListNode() : val(0), next(nullptr) {}
7 *     ListNode(int x) : val(x), next(nullptr) {}
8 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
9 * };
10 */
11class Solution {
12public:
13    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
14        ListNode* dummyHead = new ListNode(0);
15        ListNode* current = dummyHead;
16        int carry = 0;
17
18        // Iterate while there are nodes to process or a carry remains
19        while (l1 != nullptr || l2 != nullptr || carry != 0) {
20            int x = (l1 != nullptr) ? l1->val : 0;
21            int y = (l2 != nullptr) ? l2->val : 0;
22            
23            int sum = x + y + carry;
24            carry = sum / 10;
25            
26            current->next = new ListNode(sum % 10);
27            current = current->next;
28            
29            if (l1 != nullptr) l1 = l1->next;
30            if (l2 != nullptr) l2 = l2->next;
31        }
32        
33        return dummyHead->next;
34    }
35};

Java Solution for LeetCode 2

1/**
2 * Definition for singly-linked list.
3 * public class ListNode {
4 *     int val;
5 *     ListNode next;
6 *     ListNode() {}
7 *     ListNode(int val) { this.val = val; }
8 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
9 * }
10 */
11class Solution {
12    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
13        ListNode dummyHead = new ListNode(0);
14        ListNode current = dummyHead;
15        int carry = 0;
16        
17        // Loop continues until both lists end and carry is resolved
18        while (l1 != null || l2 != null || carry != 0) {
19            int x = (l1 != null) ? l1.val : 0;
20            int y = (l2 != null) ? l2.val : 0;
21            
22            int sum = x + y + carry;
23            carry = sum / 10;
24            
25            current.next = new ListNode(sum % 10);
26            current = current.next;
27            
28            if (l1 != null) l1 = l1.next;
29            if (l2 != null) l2 = l2.next;
30        }
31        
32        return dummyHead.next;
33    }
34}

Python Solution for LeetCode 2

1# Definition for singly-linked list.
2# class ListNode:
3#     def __init__(self, val=0, next=None):
4#         self.val = val
5#         self.next = next
6class Solution:
7    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
8        dummy_head = ListNode(0)
9        current = dummy_head
10        carry = 0
11        
12        # Continue if either list has nodes or there is a carry
13        while l1 is not None or l2 is not None or carry != 0:
14            x = l1.val if l1 is not None else 0
15            y = l2.val if l2 is not None else 0
16            
17            total = x + y + carry
18            carry = total // 10
19            
20            current.next = ListNode(total % 10)
21            current = current.next
22            
23            if l1 is not None:
24                l1 = l1.next
25            if l2 is not None:
26                l2 = l2.next
27                
28        return dummy_head.next