Add Two Numbers Linked List Solution

The Add Two Numbers problem requires adding two numbers represented as linked lists where each node contains a single digit in reverse order. This classic algorithmic challenge tests understanding of linked list manipulation, carry propagation, and edge case handling in technical interviews.

1. Problem Restatement

Clarifying questions to ask the interviewer:

1. Are the input linked lists guaranteed to be non-empty, or should we handle empty inputs?
2. Do the linked lists represent numbers in most-significant-digit-first order or least-significant-digit-first order?
3. Can we modify the input linked lists, or must we create a new result list?
4. What is the maximum length of the input lists and what are the constraints on node values (0-9)?
5. Should we return a new list or can we mutate one of the inputs?

Restatement in my own words: We are given two non-empty linked lists representing two non-negative integers. Each node contains a single digit, and digits are stored in reverse order (least significant digit first). We need to add these two numbers and return the sum as a linked list in the same format.

Clarifying inputs, outputs, and constraints:

• Input: Two linked lists where each node contains a digit (0-9)
• Output: A new linked list representing the sum of the two numbers
• Each list represents a number in reverse order (e.g., [2,4,3] represents 342)
• The result must also be in reverse order
• Each number is guaranteed to fit within the integer range (or long, depending on constraints)
• Lists can have different lengths

Assumptions I'm making:

1. The input lists are valid linked lists with at least one node
2. Each node contains a single digit (0-9)
3. The lists represent numbers in reverse order (LSB first)
4. We can create a new list rather than modifying inputs
5. The result should be returned as a new linked list

Data shape and hidden structure: The problem presents two linked lists where each node represents a digit in reverse order. The mathematical structure is that we're performing addition with carry propagation, similar to how we add numbers manually on paper. The key insight is that the lists are already aligned by position (digits at same index represent same place values), so we can process them simultaneously from left to right, maintaining a carry variable for overflow.

The structure is inherently sequential - we process digits from least to most significant, and carry propagation affects subsequent operations. This suggests a linear scan approach with O(1) space for carrying forward intermediate results.

2. Pattern Recognition

The problem asks us to add two numbers represented as linked lists where each node contains a single digit and digits are stored in reverse order (least significant digit first). This is a classic example of digit-by-digit addition with carry propagation.

The key patterns that signal this approach:

• Linked list traversal: We need to process nodes sequentially from head to tail
• Carry management: When digit sum exceeds 9, we must carry the overflow to the next position
• Unequal length handling: The two numbers might have different lengths, requiring careful boundary condition handling
• Reverse order processing: Digits are already stored in reverse order, making the addition process natural

This problem fits the simulation/implementation pattern where we're essentially simulating how we would manually add two numbers on paper, with the added complexity that our data structure is a linked list rather than an array or string.

The core insight is that we're performing base-10 arithmetic with carry propagation, where each step involves:

1. Adding corresponding digits from both lists
2. Managing the carry from previous operations
3. Creating new nodes for the result
4. Handling remaining digits in longer lists

This pattern is fundamental to many arithmetic operations and digital circuit design problems, making it a strong candidate for the "simulation" category in DSA interviews.

3. Approach Evolution

My first instinct is to simulate the addition process we do manually, digit by digit from right to left, keeping track of carry. But that would require reversing the linked lists or using extra space to store results in reverse order, which isn't optimal. Let me think about how to optimize this.

The brute force approach would be to convert both linked lists to integers, add them, then convert back to a linked list. But this has several problems: it doesn't handle very large numbers that exceed integer/long limits, and it's inefficient in terms of space and time complexity.

A better approach is to simulate the addition directly on the linked lists while maintaining a carry. I notice that if I process both lists simultaneously from left to right and maintain the invariant that I'm always adding corresponding digits (or 0 if one list is shorter) along with the carry, I can build the result list in one pass.

The key optimization here is to process nodes from left to right (most significant digit first) and handle the carry propagation correctly. I need to ensure that when one list is shorter, I treat its remaining digits as 0, and I continue processing until both lists are exhausted and there's no carry left.

The core insight is that since we're adding numbers, the result can be at most one digit longer than the longer input list. By processing from left to right and maintaining carry, we can build the result list in a single pass without needing to reverse or store intermediate results.

Here's my step-by-step approach:

1. Initialize a dummy head for result list and a carry variable
2. Process both lists simultaneously while they have nodes
3. For each position, calculate sum of digits + carry
4. Create new node with (sum % 10) and update carry = sum / 10
5. Continue until both lists are exhausted and carry is 0
6. Return the next of dummy head as result

This approach maintains the invariant that at each step, I'm correctly computing the digit and carry for that position in the final sum.

4. Data Structure Choice

For the "Add Two Numbers" problem, I'll use a linked list as my primary data structure.

The problem explicitly provides two linked lists representing non-negative integers in reverse order (least significant digit first), so the linked list is the natural and required data structure for this problem.

Why linked lists are needed:

• The input is given as linked lists, so we must work with this structure
• Each node contains a single digit (0-9) and a pointer to the next node
• The result must also be returned as a linked list in the same format

Time and space impact:

• Time complexity is O(max(m,n)) where m and n are the lengths of the input lists
• Space complexity is O(max(m,n)) for the result list
• We don't need additional data structures like hash maps or trees since we're simply traversing and combining the lists sequentially

Helper structure considerations:

• We don't need any additional helper data structures beyond the basic linked list nodes
• A dummy head node can be useful to simplify edge case handling (like when we need to build the result list from scratch)
• The carry value can be tracked with a simple integer variable rather than any complex data structure

The linked list is the fundamental data structure here - there's no meaningful alternative that would simplify the problem or improve performance, since we're literally combining two linked lists digit-by-digit with carry propagation.

5. Algorithm Walkthrough

Let me trace through the algorithm using the example where l1 = [2,4,3] and l2 = [5,6,4], representing numbers 342 + 465 = 807.

Step 1: Initialize carry = 0, resultHead = null, current = null

Step 2: Process first nodes: l1.val = 2, l2.val = 5

• Sum = 2 + 5 + 0 = 7
• Digit = 7 % 10 = 7
• Carry = 7 / 10 = 0
• Create new node with value 7
• Set resultHead to this node (first node)
• current = resultHead

Step 3: Process second nodes: l1.val = 4, l2.val = 6

• Sum = 4 + 6 + 0 = 10
• Digit = 10 % 10 = 0
• Carry = 10 / 10 = 1
• Create new node with value 0
• Link to current node's next
• current = current.next

Step 4: Process third nodes: l1.val = 3, l2.val = 4

• Sum = 3 + 4 + 1 = 8
• Digit = 8 % 10 = 8
• Carry = 8 / 10 = 0
• Create new node with value 8
• Link to current node's next
• current = current.next

Step 5: Both lists exhausted, carry = 0

• No additional node needed
• Return resultHead which points to the head of our result list

The algorithm correctly produces [7,0,8] representing 807.

Edge case handling:

• When one list is longer, we continue processing the remaining nodes with carry
• When lists are different lengths, we treat missing nodes as 0
• Final carry is handled by potentially adding one more node

The algorithm terminates correctly because we process all nodes and handle any remaining carry.

6. Java Solution

/**
 * 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) {
        // Create a dummy head to simplify list construction
        ListNode dummyHead = new ListNode(0);
        ListNode current = dummyHead;
        int carry = 0;
        
        // Process each digit while at least one list has remaining nodes
        while (l1 != null || l2 != null) {
            // Get the values from current nodes (0 if node is null)
            int val1 = (l1 != null) ? l1.val : 0;
            int val2 = (l2 != null) ? l2.val : 0;
            
            // Calculate sum and new carry
            int sum = val1 + val2 + carry;
            carry = sum / 10;
            int digit = sum % 10;
            
            // Create new node with the digit and advance pointer
            current.next = new ListNode(digit);
            current = current.next;
            
            // Move to next nodes if available
            l1 = (l1 != null) ? l1.next : null;
            l2 = (l2 != null) ? l2.next : null;
        }
        
        // Handle final carry if needed
        if (carry > 0) {
            current.next = new ListNode(carry);
        }
        
        // Return the actual result list (skip dummy head)
        return dummyHead.next;
    }
}

This solution simulates the manual addition process we perform on paper, processing digits from least significant to most significant. It uses a dummy head node to simplify the list construction logic and handles all edge cases including different length lists and final carry propagation. The approach is clean, readable, and handles all constraints properly.

7. Complexity Analysis

Time Complexity: O(max(m,n))

Where m and n are the lengths of the two input linked lists representing the numbers. We need to traverse each list once to process all digits, and the number of operations is proportional to the length of the longer list. Each node is visited exactly once, making this optimal for the problem constraints.

Space Complexity: O(max(m,n))

The space complexity comes from the result linked list we create to store the sum. In the worst case, when there's a carry at every position (e.g., 999 + 1 = 1000), the result list will have one more node than the longer input list. Therefore, space usage is linear in the length of the longer input list.

Why these bounds are correct:

• The time complexity is tight because we must process each digit at least once to compute the sum
• The space complexity is tight because we must create a new node for each digit in the result, including potential carry overflow
• There's no way to avoid visiting all nodes in at least one list, and we must store the complete result

Optimality:

This solution is optimal for the problem as stated. We cannot do better than O(max(m,n)) time because we must read all input digits, and we cannot do better than O(max(m,n)) space because we must store the complete result. The solution achieves both bounds optimally.

The algorithm is optimal because:

1. It processes each input digit exactly once
2. It creates the minimal necessary output structure
3. It avoids any redundant operations or extra passes through data

8. Edge Cases & Pitfalls

Empty and Minimal Inputs

• Empty lists: When one or both input lists are null, we must handle gracefully. The problem definition typically assumes valid ListNode objects, but edge case handling is still important.
• Single node lists: Lists with just one node (e.g., [5] + [7]) should work correctly without special handling.

Duplicate Values and Repeated States

• Carry propagation: When adding digits results in carry, we must ensure that carry is properly propagated through subsequent digits. For example: 999 + 1 = 1000.
• Digit overflow: Adding two single digits can produce a two-digit result (e.g., 7 + 8 = 15), requiring proper carry handling.

Boundary Conditions

• Different list lengths: One list may be longer than the other, requiring careful handling of remaining nodes.
• Final carry: If there's a carry after processing all digits, we must create an additional node for the carry (e.g., 99 + 1 = 100).
• Zero handling: Lists containing zeros (e.g., [0] + [0]) must return [0], not [0, 0].

Common Implementation Mistakes

• Not handling carry properly: Forgetting to include the carry in subsequent additions or not carrying over to new nodes.
• Incorrect null pointer handling: Accessing next node without checking for null, leading to NullPointerException.
• Missing final carry: Failing to create a new node when there's a remaining carry after processing all digits.
• Modifying input lists: Mutating the original input ListNode objects instead of creating new ones, which violates expected behavior.
• Incorrect list construction: Building the result list in reverse order instead of maintaining proper node linking.

Implementation Considerations

// Common mistake - missing carry at end:
ListNode dummy = new ListNode(0);
ListNode current = dummy;
int carry = 0;

// ... processing loop ...

// Missing this check:
if (carry > 0) {
    current.next = new ListNode(carry);
}

The key is ensuring that every possible path through the algorithm creates a valid result list with proper node linking and carry handling.

9. Alternative Approaches

There are several alternative approaches to solving the "Add Two Numbers" problem, each with different trade-offs:

1. Recursive Approach: Instead of using iteration, we could implement a recursive solution that processes nodes one by one. The recursion would naturally handle the carry propagation, but it would use O(max(m,n)) space on the call stack. This approach is less efficient for large inputs due to stack overflow risk and additional memory overhead.

2. String-based Approach: Convert both linked lists to strings, reverse them, perform string addition with carry, then convert back to a linked list. This approach is conceptually simpler but less efficient as it requires O(m+n) extra space for string operations and additional time complexity for string manipulation.

3. Reverse Lists First: Reverse both input lists first, then perform addition from left to right (which becomes right to left in the original), and finally reverse the result. This approach requires additional O(m+n) space for the reversed lists and extra traversal time, making it less efficient than the direct approach.

4. Using BigInteger: For extremely large numbers, we could use Java's BigInteger class to handle arbitrarily large integers. While this simplifies the implementation, it introduces unnecessary overhead for typical use cases and doesn't align with the problem's intent to simulate manual addition.

The chosen iterative approach is preferred because it maintains optimal O(1) space complexity, processes nodes in a single pass, and directly simulates the manual addition algorithm without unnecessary transformations or additional space requirements.

The direct iterative solution is superior in terms of both time and space efficiency, making it the most practical choice for real-world implementation.

10. Test Cases

// Test case 1: Basic case with no carry
// Input: l1 = [2,4,3], l2 = [5,6,4]
// Expected: [7,0,8] (342 + 465 = 807)
ListNode l1_1 = new ListNode(2);
l1_1.next = new ListNode(4);
l1_1.next.next = new ListNode(3);

ListNode l2_1 = new ListNode(5);
l2_1.next = new ListNode(6);
l2_1.next.next = new ListNode(4);

// Test case 2: Carry propagation
// Input: l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
// Expected: [8,9,9,9,0,0,0,1] (9999999 + 9999 = 10009998)
ListNode l1_2 = new ListNode(9);
l1_2.next = new ListNode(9);
l1_2.next.next = new ListNode(9);
l1_2.next.next.next = new ListNode(9);
l1_2.next.next.next.next = new ListNode(9);
l1_2.next.next.next.next.next = new ListNode(9);
l1_2.next.next.next.next.next.next = new ListNode(9);

ListNode l2_2 = new ListNode(9);
l2_2.next = new ListNode(9);
l2_2.next.next = new ListNode(9);
l2_2.next.next.next = new ListNode(9);

// Test case 3: Different lengths
// Input: l1 = [9,9], l2 = [1,2,3]
// Expected: [0,2,4] (99 + 123 = 222)
ListNode l1_3 = new ListNode(9);
l1_3.next = new ListNode(9);

ListNode l2_3 = new ListNode(1);
l2_3.next = new ListNode(2);
l2_3.next.next = new ListNode(3);

// Test case 4: Empty lists
// Input: l1 = [], l2 = []
// Expected: []
ListNode l1_4 = null;
ListNode l2_4 = null;

// Test case 5: One empty list
// Input: l1 = [0], l2 = []
// Expected: [0]
ListNode l1_5 = new ListNode(0);
ListNode l2_5 = null;

The test cases cover:

1. Basic addition without carry propagation
2. Carry propagation across all digits with different lengths
3. Lists of different lengths
4. Empty input lists
5. One empty list with a zero node

Each test case validates different aspects of the algorithm including digit-by-digit addition, carry handling, and boundary conditions. The test cases ensure that edge cases like empty lists and different input sizes are properly handled by the solution.

11. Final Summary

The core idea is to simulate elementary addition with linked lists, processing digits from least to most significant while maintaining carry propagation. This solution works efficiently by leveraging the natural structure of linked lists to avoid reversing or extra space overhead, achieving optimal O(max(m,n)) time and O(max(m,n)) space complexity where m and n are the lengths of the input lists. The approach elegantly handles all edge cases including different length lists, carry propagation, and empty inputs through careful pointer management and boundary condition handling.