Add Two Numbers

Add two numbers represented as linked lists where digits are stored in reverse order

Language Selection

Choose your preferred programming language

Showing: Python

Problem Statement

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Input/Output Specifications

Input: Two non-empty linked lists representing numbers in reverse order
Output: Linked list representing the sum in reverse order
Constraints:
- The number of nodes in each linked list is in the range [1, 100]
- 0 <= Node.val <= 9
- It is guaranteed that the list represents a number that does not have leading zeros

Examples

Example 1:

Input: l1 = [2,4,3], l2 = [5,6,4]
Output: [7,0,8]
Explanation: 342 + 465 = 807

Example 2:

Input: l1 = [0], l2 = [0]
Output: [0]

Example 3:

Input: l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
Output: [8,9,9,9,0,0,0,1]

Solutions

Approach 1: Elementary Math Simulation

This approach simulates the addition process digit by digit, handling carry propagation naturally.

Algorithm:

Initialize a dummy head and current pointer for result
Initialize carry to 0
While either list has nodes or carry is non-zero:
- Calculate sum of current digits plus carry
- Create new node with sum % 10
- Update carry to sum / 10
- Move to next nodes in both lists
Return the head of result list (skip dummy)

Python:

def addTwoNumbers(l1, l2):
    """
    Add two numbers represented as linked lists
    Time: O(max(m, n))
    Space: O(max(m, n))
    """
    dummy = ListNode(0)
    current = dummy
    carry = 0
    
    while l1 or l2 or carry:
        # Calculate sum of current digits plus carry
        val1 = l1.val if l1 else 0
        val2 = l2.val if l2 else 0
        total = val1 + val2 + carry
        
        # Create new node with sum % 10
        current.next = ListNode(total % 10)
        current = current.next
        
        # Update carry
        carry = total // 10
        
        # Move to next nodes
        l1 = l1.next if l1 else None
        l2 = l2.next if l2 else None
    
    return dummy.next

Java:

class Solution {
    /**
     * Add two numbers represented as linked lists
     * Time: O(max(m, n))
     * Space: O(max(m, n))
     */
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0);
        ListNode current = dummy;
        int carry = 0;
        
        while (l1 != null || l2 != null || carry != 0) {
            // Calculate sum of current digits plus carry
            int val1 = (l1 != null) ? l1.val : 0;
            int val2 = (l2 != null) ? l2.val : 0;
            int total = val1 + val2 + carry;
            
            // Create new node with sum % 10
            current.next = new ListNode(total % 10);
            current = current.next;
            
            // Update carry
            carry = total / 10;
            
            // Move to next nodes
            l1 = (l1 != null) ? l1.next : null;
            l2 = (l2 != null) ? l2.next : null;
        }
        
        return dummy.next;
    }
}

Go:

// addTwoNumbers - Add two numbers represented as linked lists
// Time: O(max(m, n))
// Space: O(max(m, n))
func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
    dummy := &ListNode{Val: 0}
    current := dummy
    carry := 0
    
    for l1 != nil || l2 != nil || carry != 0 {
        // Calculate sum of current digits plus carry
        val1 := 0
        if l1 != nil {
            val1 = l1.Val
        }
        val2 := 0
        if l2 != nil {
            val2 = l2.Val
        }
        total := val1 + val2 + carry
        
        // Create new node with sum % 10
        current.Next = &ListNode{Val: total % 10}
        current = current.Next
        
        // Update carry
        carry = total / 10
        
        // Move to next nodes
        if l1 != nil {
            l1 = l1.Next
        }
        if l2 != nil {
            l2 = l2.Next
        }
    }
    
    return dummy.Next
}

JavaScript:

/**
 * Add two numbers represented as linked lists
 * Time: O(max(m, n))
 * Space: O(max(m, n))
 */
function addTwoNumbers(l1, l2) {
    const dummy = new ListNode(0);
    let current = dummy;
    let carry = 0;
    
    while (l1 !== null || l2 !== null || carry !== 0) {
        // Calculate sum of current digits plus carry
        const val1 = l1 !== null ? l1.val : 0;
        const val2 = l2 !== null ? l2.val : 0;
        const total = val1 + val2 + carry;
        
        // Create new node with sum % 10
        current.next = new ListNode(total % 10);
        current = current.next;
        
        // Update carry
        carry = Math.floor(total / 10);
        
        // Move to next nodes
        l1 = l1 !== null ? l1.next : null;
        l2 = l2 !== null ? l2.next : null;
    }
    
    return dummy.next;
}

C#:

public class Solution {
    /// <summary>
    /// Add two numbers represented as linked lists
    /// Time: O(max(m, n))
    /// Space: O(max(m, n))
    /// </summary>
    public ListNode AddTwoNumbers(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0);
        ListNode current = dummy;
        int carry = 0;
        
        while (l1 != null || l2 != null || carry != 0) {
            // Calculate sum of current digits plus carry
            int val1 = l1?.val ?? 0;
            int val2 = l2?.val ?? 0;
            int total = val1 + val2 + carry;
            
            // Create new node with sum % 10
            current.next = new ListNode(total % 10);
            current = current.next;
            
            // Update carry
            carry = total / 10;
            
            // Move to next nodes
            l1 = l1?.next;
            l2 = l2?.next;
        }
        
        return dummy.next;
    }
}

Approach 2: Recursive Solution

This approach uses recursion to add the numbers, handling carry through the call stack.

Algorithm:

Base case: if both lists are null and carry is 0, return null
Calculate sum of current digits plus carry
Create new node with sum % 10
Recursively add the remaining digits
Return the current node

Python:

def addTwoNumbersRecursive(l1, l2, carry=0):
    """
    Add two numbers using recursion
    Time: O(max(m, n))
    Space: O(max(m, n)) - due to recursion stack
    """
    if not l1 and not l2 and carry == 0:
        return None
    
    val1 = l1.val if l1 else 0
    val2 = l2.val if l2 else 0
    total = val1 + val2 + carry
    
    node = ListNode(total % 10)
    node.next = addTwoNumbersRecursive(
        l1.next if l1 else None,
        l2.next if l2 else None,
        total // 10
    )
    
    return node

Java:

class Solution {
    /**
     * Add two numbers using recursion
     * Time: O(max(m, n))
     * Space: O(max(m, n)) - due to recursion stack
     */
    public ListNode addTwoNumbersRecursive(ListNode l1, ListNode l2) {
        return addTwoNumbersRecursive(l1, l2, 0);
    }
    
    private ListNode addTwoNumbersRecursive(ListNode l1, ListNode l2, int carry) {
        if (l1 == null && l2 == null && carry == 0) {
            return null;
        }
        
        int val1 = (l1 != null) ? l1.val : 0;
        int val2 = (l2 != null) ? l2.val : 0;
        int total = val1 + val2 + carry;
        
        ListNode node = new ListNode(total % 10);
        node.next = addTwoNumbersRecursive(
            (l1 != null) ? l1.next : null,
            (l2 != null) ? l2.next : null,
            total / 10
        );
        
        return node;
    }
}

Go:

// addTwoNumbersRecursive - Add two numbers using recursion
// Time: O(max(m, n))
// Space: O(max(m, n)) - due to recursion stack
func addTwoNumbersRecursive(l1 *ListNode, l2 *ListNode) *ListNode {
    return addTwoNumbersRecursiveHelper(l1, l2, 0)
}

func addTwoNumbersRecursiveHelper(l1 *ListNode, l2 *ListNode, carry int) *ListNode {
    if l1 == nil && l2 == nil && carry == 0 {
        return nil
    }
    
    val1 := 0
    if l1 != nil {
        val1 = l1.Val
    }
    val2 := 0
    if l2 != nil {
        val2 = l2.Val
    }
    total := val1 + val2 + carry
    
    node := &ListNode{Val: total % 10}
    nextL1 := l1
    if l1 != nil {
        nextL1 = l1.Next
    }
    nextL2 := l2
    if l2 != nil {
        nextL2 = l2.Next
    }
    node.Next = addTwoNumbersRecursiveHelper(nextL1, nextL2, total/10)
    
    return node
}

JavaScript:

/**
 * Add two numbers using recursion
 * Time: O(max(m, n))
 * Space: O(max(m, n)) - due to recursion stack
 */
function addTwoNumbersRecursive(l1, l2, carry = 0) {
    if (l1 === null && l2 === null && carry === 0) {
        return null;
    }
    
    const val1 = l1 !== null ? l1.val : 0;
    const val2 = l2 !== null ? l2.val : 0;
    const total = val1 + val2 + carry;
    
    const node = new ListNode(total % 10);
    node.next = addTwoNumbersRecursive(
        l1 !== null ? l1.next : null,
        l2 !== null ? l2.next : null,
        Math.floor(total / 10)
    );
    
    return node;
}

C#:

public class Solution {
    /// <summary>
    /// Add two numbers using recursion
    /// Time: O(max(m, n))
    /// Space: O(max(m, n)) - due to recursion stack
    /// </summary>
    public ListNode AddTwoNumbersRecursive(ListNode l1, ListNode l2) {
        return AddTwoNumbersRecursive(l1, l2, 0);
    }
    
    private ListNode AddTwoNumbersRecursive(ListNode l1, ListNode l2, int carry) {
        if (l1 == null && l2 == null && carry == 0) {
            return null;
        }
        
        int val1 = l1?.val ?? 0;
        int val2 = l2?.val ?? 0;
        int total = val1 + val2 + carry;
        
        ListNode node = new ListNode(total % 10);
        node.next = AddTwoNumbersRecursive(
            l1?.next,
            l2?.next,
            total / 10
        );
        
        return node;
    }
}

Key Insights

Elementary math simulation: Mimics how we add numbers on paper
Carry handling: Properly propagate carry to the next digit
Dummy node: Simplifies edge cases and result construction
Unequal lengths: Handle lists of different lengths naturally
Reverse order: The reverse order makes addition easier (no need to reverse)

Edge Cases

Lists of different lengths
Carry propagation at the end
Both lists are single digits
One list is empty (edge case)
Large numbers causing multiple carries

Test Cases

# Test case 1: Normal addition
l1 = ListNode(2)
l1.next = ListNode(4)
l1.next.next = ListNode(3)

l2 = ListNode(5)
l2.next = ListNode(6)
l2.next.next = ListNode(4)
# Expected: [7,0,8] (342 + 465 = 807)

# Test case 2: Different lengths
l3 = ListNode(9)
l3.next = ListNode(9)
l3.next.next = ListNode(9)

l4 = ListNode(9)
l4.next = ListNode(9)
# Expected: [8,9,0,1] (999 + 99 = 1098)

# Test case 3: Single digits
l5 = ListNode(5)
l6 = ListNode(5)
# Expected: [0,1] (5 + 5 = 10)

Follow-up Questions

How would you handle numbers in forward order?
Can you optimize for space if one list is much shorter?
How would you handle negative numbers?
What if the numbers are very large?

Common Mistakes

Not handling carry properly
Forgetting to create new nodes for the result
Not handling lists of different lengths
Incorrect carry calculation
Not handling the final carry
Memory leaks when not properly managing pointers