Add Two Numbers

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 in the same reverse order.

What to notice first

• The digits are stored in reverse order, so the head of the list is the ones place, the next node is the tens place, etc.
• You must handle carries propagating through the list, just like elementary school addition.
• The result list may have more nodes than either input list if a carry propagates beyond the last digit.
• Both lists may have different lengths; treat missing nodes as zero.

Examples

l1	l2	Output	Explanation
[2, 4, 3]	[5, 6, 4]	[7, 0, 8]	342 + 465 = 807 (reversed)
[0]	[0]	[0]	0 + 0 = 0
[9,9,9,9,9,9,9]	[9,9,9,9]	[8,9,9,9,0,0,0,1]	9999999 + 9999 = 10009998 (reversed)

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.

Real-World Applications

Where this pattern appears

• Big integer arithmetic — systems that need to add numbers larger than language-native integer types (Bitcoin addresses, cryptography libraries).
• Polynomial representation — coefficients in reverse order (lowest power first) allow direct term-by-term addition.
• Time-series accumulation — rolling aggregation of digits from streaming data (sensor readings, signal processing).
• Arbitrary precision math libraries — implementing addition for Python’s unlimited integers or similar systems.
• Ledger systems — combining transaction chains where digits represent atomic units.

Complexity Comparison

Approach	Time	Space	Call Stack	Best When
Iterative	O(max(m, n))	O(max(m, n))	Minimal	General case — clean, no recursion overhead
Recursive	O(max(m, n))	O(max(m, n))	O(max(m, n))	Learning recursion, practicing self-similar structure

* Space refers to output list size. Both approaches handle carries efficiently.

Which approach should you learn first?

• Pick Iterative if you want the most straightforward, predictable solution.
• Pick Recursive if you are practicing recursion or want to see how the problem mirrors itself at each digit.

Recommended

Iterative

O(max(m, n)) time · O(max(m, n)) space

Educational

Recursive

O(max(m, n)) time · O(max(m, n)) space

Approach 1: Iterative with Carry (Recommended)

★ Recommended

Walk through both lists simultaneously, adding digits column-by-column and propagating the carry forward.

Use a dummy node at the start to simplify list construction. At each step, compute the sum of the two digit values plus any carry from the previous step, extract the new carry, and create a new node for the result digit.

⏱ Time O(max(m, n)) One pass through lists 💾 Space O(max(m, n)) Output list size

Step-by-step Example

Input: l1 = [2, 4, 3] (342), l2 = [5, 6, 4] (465)

Step	l1	l2	carry	sum	digit	new_carry	result
1	2	5	0	7	7	0	[7]
2	4	6	0	10	0	1	[7, 0]
3	3	4	1	8	8	0	[7, 0, 8]
Done	-	-	0	-	-	-	✓

Input: l1 = [9,9,9,9,9,9,9] (9999999), l2 = [9,9,9,9] (9999)

The carry propagates all the way through: 9999999 + 9999 = 10009998, which becomes [8,9,9,9,0,0,0,1] in reverse.

Animated walkthrough

How carry propagation works through digit-by-digit addition

Use Next or Autoplay to watch the algorithm process each digit, compute the sum with carry, and build the result list.

Back Autoplay Next Reset

Step 1 of 3 Target: max(m, n)

Waiting to begin...

Array state

Memory / lookup state

Pseudocode

function addTwoNumbers(l1, l2):
    dummy = ListNode(0)
    current = dummy
    carry = 0

    while l1 or l2 or carry:
        val1 = l1.val if l1 else 0
        val2 = l2.val if l2 else 0

        total = val1 + val2 + carry
        carry = total / 10
        digit = total % 10

        current.next = ListNode(digit)
        current = current.next

        l1 = l1.next if l1 else null
        l2 = l2.next if l2 else null

    return dummy.next

Solution Code

Python

add_two_numbers_iterative.py

from typing import Optional


class ListNode:
    def __init__(self, val: int = 0, next: Optional['ListNode'] = None):
        self.val = val
        self.next = next


def addTwoNumbers(l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
    """
    Add two numbers represented by linked lists in reverse order.

    Time Complexity: O(max(m, n)) where m and n are the lengths of the lists
    Space Complexity: O(max(m, n)) for the output list
    """
    dummy = ListNode(0)
    current = dummy
    carry = 0

    while l1 or l2 or carry:
        val1 = l1.val if l1 else 0
        val2 = l2.val if l2 else 0

        total = val1 + val2 + carry
        carry = total // 10
        digit = total % 10

        current.next = ListNode(digit)
        current = current.next

        l1 = l1.next if l1 else None
        l2 = l2.next if l2 else None

    return dummy.next


# Test cases
if __name__ == "__main__":
    # Helper function to create linked list from list
    def create_linked_list(arr):
        if not arr:
            return None
        head = ListNode(arr[0])
        current = head
        for val in arr[1:]:
            current.next = ListNode(val)
            current = current.next
        return head

    # Helper function to convert linked list to list for printing
    def linked_list_to_list(head):
        result = []
        current = head
        while current:
            result.append(current.val)
            current = current.next
        return result

    # Test case 1: [2,4,3] + [5,6,4] = [7,0,8] (342 + 465 = 807)
    l1 = create_linked_list([2, 4, 3])
    l2 = create_linked_list([5, 6, 4])
    result = addTwoNumbers(l1, l2)
    print(f"Test 1: {linked_list_to_list(result)}")  # [7, 0, 8]

    # Test case 2: [0] + [0] = [0]
    l1 = create_linked_list([0])
    l2 = create_linked_list([0])
    result = addTwoNumbers(l1, l2)
    print(f"Test 2: {linked_list_to_list(result)}")  # [0]

    # Test case 3: [9,9,9,9,9,9,9] + [9,9,9,9] = [8,9,9,9,0,0,0,1] (9999999 + 9999 = 10009998)
    l1 = create_linked_list([9, 9, 9, 9, 9, 9, 9])
    l2 = create_linked_list([9, 9, 9, 9])
    result = addTwoNumbers(l1, l2)
    print(f"Test 3: {linked_list_to_list(result)}")  # [8, 9, 9, 9, 0, 0, 0, 1]

C++

add_two_numbers_iterative.cpp

#include <iostream>
#include <vector>

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x = 0) : val(x), next(nullptr) {}
};

ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
    /*
    Add two numbers represented by linked lists in reverse order.

    Time Complexity: O(max(m, n)) where m and n are the lengths of the lists
    Space Complexity: O(max(m, n)) for the output list
    */
    ListNode* dummy = new ListNode(0);
    ListNode* current = dummy;
    int carry = 0;

    while (l1 || l2 || carry) {
        int val1 = l1 ? l1->val : 0;
        int val2 = l2 ? l2->val : 0;

        int total = val1 + val2 + carry;
        carry = total / 10;
        int digit = total % 10;

        current->next = new ListNode(digit);
        current = current->next;

        l1 = l1 ? l1->next : nullptr;
        l2 = l2 ? l2->next : nullptr;
    }

    ListNode* result = dummy->next;
    delete dummy;
    return result;
}

// Helper function to create linked list from vector
ListNode* createLinkedList(const std::vector<int>& arr) {
    if (arr.empty()) return nullptr;
    ListNode* head = new ListNode(arr[0]);
    ListNode* current = head;
    for (size_t i = 1; i < arr.size(); i++) {
        current->next = new ListNode(arr[i]);
        current = current->next;
    }
    return head;
}

// Helper function to print linked list
void printLinkedList(ListNode* head) {
    std::cout << "[";
    bool first = true;
    while (head) {
        if (!first) std::cout << ", ";
        std::cout << head->val;
        head = head->next;
        first = false;
    }
    std::cout << "]" << std::endl;
}

// Helper function to delete linked list
void deleteLinkedList(ListNode* head) {
    while (head) {
        ListNode* temp = head;
        head = head->next;
        delete temp;
    }
}

int main() {
    // Test case 1: [2,4,3] + [5,6,4] = [7,0,8] (342 + 465 = 807)
    ListNode* l1 = createLinkedList({2, 4, 3});
    ListNode* l2 = createLinkedList({5, 6, 4});
    ListNode* result = addTwoNumbers(l1, l2);
    std::cout << "Test 1: ";
    printLinkedList(result);
    deleteLinkedList(result);

    // Test case 2: [0] + [0] = [0]
    l1 = createLinkedList({0});
    l2 = createLinkedList({0});
    result = addTwoNumbers(l1, l2);
    std::cout << "Test 2: ";
    printLinkedList(result);
    deleteLinkedList(result);

    // Test case 3: [9,9,9,9,9,9,9] + [9,9,9,9] = [8,9,9,9,0,0,0,1]
    l1 = createLinkedList({9, 9, 9, 9, 9, 9, 9});
    l2 = createLinkedList({9, 9, 9, 9});
    result = addTwoNumbers(l1, l2);
    std::cout << "Test 3: ";
    printLinkedList(result);
    deleteLinkedList(result);

    return 0;
}

Java

add_two_numbers_iterative.java

import java.util.ArrayList;
import java.util.List;

class ListNode {
    int val;
    ListNode next;
    ListNode(int x) {
        val = x;
    }
}

public class add_two_numbers_iterative {
    /**
     * Add two numbers represented by linked lists in reverse order.
     *
     * Time Complexity: O(max(m, n)) where m and n are the lengths of the lists
     * Space Complexity: O(max(m, n)) for the output list
     */
    public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0);
        ListNode current = dummy;
        int carry = 0;

        while (l1 != null || l2 != null || carry != 0) {
            int val1 = l1 != null ? l1.val : 0;
            int val2 = l2 != null ? l2.val : 0;

            int total = val1 + val2 + carry;
            carry = total / 10;
            int digit = total % 10;

            current.next = new ListNode(digit);
            current = current.next;

            l1 = l1 != null ? l1.next : null;
            l2 = l2 != null ? l2.next : null;
        }

        return dummy.next;
    }

    // Helper function to create linked list from array
    private static ListNode createLinkedList(int[] arr) {
        if (arr.length == 0) return null;
        ListNode head = new ListNode(arr[0]);
        ListNode current = head;
        for (int i = 1; i < arr.length; i++) {
            current.next = new ListNode(arr[i]);
            current = current.next;
        }
        return head;
    }

    // Helper function to convert linked list to list for printing
    private static List<Integer> linkedListToList(ListNode head) {
        List<Integer> result = new ArrayList<>();
        ListNode current = head;
        while (current != null) {
            result.add(current.val);
            current = current.next;
        }
        return result;
    }

    public static void main(String[] args) {
        // Test case 1: [2,4,3] + [5,6,4] = [7,0,8] (342 + 465 = 807)
        ListNode l1 = createLinkedList(new int[]{2, 4, 3});
        ListNode l2 = createLinkedList(new int[]{5, 6, 4});
        ListNode result = addTwoNumbers(l1, l2);
        System.out.println("Test 1: " + linkedListToList(result));  // [7, 0, 8]

        // Test case 2: [0] + [0] = [0]
        l1 = createLinkedList(new int[]{0});
        l2 = createLinkedList(new int[]{0});
        result = addTwoNumbers(l1, l2);
        System.out.println("Test 2: " + linkedListToList(result));  // [0]

        // Test case 3: [9,9,9,9,9,9,9] + [9,9,9,9] = [8,9,9,9,0,0,0,1]
        l1 = createLinkedList(new int[]{9, 9, 9, 9, 9, 9, 9});
        l2 = createLinkedList(new int[]{9, 9, 9, 9});
        result = addTwoNumbers(l1, l2);
        System.out.println("Test 3: " + linkedListToList(result));  // [8, 9, 9, 9, 0, 0, 0, 1]
    }
}

JavaScript

add_two_numbers_iterative.js

/**
 * Definition for singly-linked list node.
 */
class ListNode {
    constructor(val = 0, next = null) {
        this.val = val;
        this.next = next;
    }
}

/**
 * Add two numbers represented by linked lists in reverse order.
 *
 * Time Complexity: O(max(m, n)) where m and n are the lengths of the lists
 * Space Complexity: O(max(m, n)) for the output list
 *
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
const addTwoNumbers = (l1, l2) => {
    const dummy = new ListNode(0);
    let current = dummy;
    let carry = 0;

    while (l1 || l2 || carry) {
        const val1 = l1 ? l1.val : 0;
        const val2 = l2 ? l2.val : 0;

        const total = val1 + val2 + carry;
        carry = Math.floor(total / 10);
        const digit = total % 10;

        current.next = new ListNode(digit);
        current = current.next;

        l1 = l1 ? l1.next : null;
        l2 = l2 ? l2.next : null;
    }

    return dummy.next;
};

// Helper function to create linked list from array
const createLinkedList = (arr) => {
    if (arr.length === 0) return null;
    const head = new ListNode(arr[0]);
    let current = head;
    for (let i = 1; i < arr.length; i++) {
        current.next = new ListNode(arr[i]);
        current = current.next;
    }
    return head;
};

// Helper function to convert linked list to array for printing
const linkedListToArray = (head) => {
    const result = [];
    let current = head;
    while (current) {
        result.push(current.val);
        current = current.next;
    }
    return result;
};

// Test cases
if (require.main === module) {
    // Test case 1: [2,4,3] + [5,6,4] = [7,0,8] (342 + 465 = 807)
    let l1 = createLinkedList([2, 4, 3]);
    let l2 = createLinkedList([5, 6, 4]);
    let result = addTwoNumbers(l1, l2);
    console.log("Test 1:", linkedListToArray(result));  // [7, 0, 8]

    // Test case 2: [0] + [0] = [0]
    l1 = createLinkedList([0]);
    l2 = createLinkedList([0]);
    result = addTwoNumbers(l1, l2);
    console.log("Test 2:", linkedListToArray(result));  // [0]

    // Test case 3: [9,9,9,9,9,9,9] + [9,9,9,9] = [8,9,9,9,0,0,0,1]
    l1 = createLinkedList([9, 9, 9, 9, 9, 9, 9]);
    l2 = createLinkedList([9, 9, 9, 9]);
    result = addTwoNumbers(l1, l2);
    console.log("Test 3:", linkedListToArray(result));  // [8, 9, 9, 9, 0, 0, 0, 1]
}

module.exports = addTwoNumbers;

Rust

add_two_numbers_iterative.rs

use std::cell::RefCell;
use std::rc::Rc;

#[derive(PartialEq, Eq, Clone, Debug)]
pub struct ListNode {
    pub val: i32,
    pub next: Option<Rc<RefCell<ListNode>>>,
}

impl ListNode {
    #[inline]
    fn new(val: i32) -> Self {
        ListNode { next: None, val }
    }
}

/// Add two numbers represented by linked lists in reverse order.
///
/// Time Complexity: O(max(m, n)) where m and n are the lengths of the lists
/// Space Complexity: O(max(m, n)) for the output list
pub fn add_two_numbers(
    l1: Option<Rc<RefCell<ListNode>>>,
    l2: Option<Rc<RefCell<ListNode>>>,
) -> Option<Rc<RefCell<ListNode>>> {
    let mut dummy = Rc::new(RefCell::new(ListNode::new(0)));
    let mut current = dummy.clone();
    let mut carry = 0;
    let mut l1 = l1;
    let mut l2 = l2;

    while l1.is_some() || l2.is_some() || carry > 0 {
        let val1 = l1.as_ref().map(|node| node.borrow().val).unwrap_or(0);
        let val2 = l2.as_ref().map(|node| node.borrow().val).unwrap_or(0);

        let total = val1 + val2 + carry;
        carry = total / 10;
        let digit = total % 10;

        let new_node = Rc::new(RefCell::new(ListNode::new(digit)));
        current.borrow_mut().next = Some(new_node.clone());
        current = new_node;

        l1 = l1.and_then(|node| node.borrow_mut().next.take());
        l2 = l2.and_then(|node| node.borrow_mut().next.take());
    }

    dummy.borrow_mut().next.take()
}

// Helper function to create linked list from vector
fn create_linked_list(arr: Vec<i32>) -> Option<Rc<RefCell<ListNode>>> {
    if arr.is_empty() {
        return None;
    }

    let mut head = Rc::new(RefCell::new(ListNode::new(arr[0])));
    let mut current = head.clone();

    for &val in &arr[1..] {
        let new_node = Rc::new(RefCell::new(ListNode::new(val)));
        current.borrow_mut().next = Some(new_node.clone());
        current = new_node;
    }

    Some(head)
}

// Helper function to convert linked list to vector for printing
fn linked_list_to_vec(head: Option<Rc<RefCell<ListNode>>>) -> Vec<i32> {
    let mut result = Vec::new();
    let mut current = head;

    while let Some(node) = current {
        let borrowed = node.borrow();
        result.push(borrowed.val);
        current = borrowed.next.clone();
    }

    result
}

fn main() {
    // Test case 1: [2,4,3] + [5,6,4] = [7,0,8] (342 + 465 = 807)
    let l1 = create_linked_list(vec![2, 4, 3]);
    let l2 = create_linked_list(vec![5, 6, 4]);
    let result = add_two_numbers(l1, l2);
    println!("Test 1: {:?}", linked_list_to_vec(result));  // [7, 0, 8]

    // Test case 2: [0] + [0] = [0]
    let l1 = create_linked_list(vec![0]);
    let l2 = create_linked_list(vec![0]);
    let result = add_two_numbers(l1, l2);
    println!("Test 2: {:?}", linked_list_to_vec(result));  // [0]

    // Test case 3: [9,9,9,9,9,9,9] + [9,9,9,9] = [8,9,9,9,0,0,0,1]
    let l1 = create_linked_list(vec![9, 9, 9, 9, 9, 9, 9]);
    let l2 = create_linked_list(vec![9, 9, 9, 9]);
    let result = add_two_numbers(l1, l2);
    println!("Test 3: {:?}", linked_list_to_vec(result));  // [8, 9, 9, 9, 0, 0, 0, 1]
}

Go

add_two_numbers_iterative.go

package main

import "fmt"

type ListNode struct {
  Val  int
  Next *ListNode
}

/*
 * Add two numbers represented by linked lists in reverse order.
 *
 * Time Complexity: O(max(m, n)) where m and n are the lengths of the lists
 * Space Complexity: O(max(m, n)) for the output list
 */
func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
  dummy := &ListNode{Val: 0}
  current := dummy
  carry := 0

  for l1 != nil || l2 != nil || carry != 0 {
    val1 := 0
    if l1 != nil {
      val1 = l1.Val
    }
    val2 := 0
    if l2 != nil {
      val2 = l2.Val
    }

    total := val1 + val2 + carry
    carry = total / 10
    digit := total % 10

    current.Next = &ListNode{Val: digit}
    current = current.Next

    if l1 != nil {
      l1 = l1.Next
    }
    if l2 != nil {
      l2 = l2.Next
    }
  }

  return dummy.Next
}

// Helper function to create linked list from array
func createLinkedList(arr []int) *ListNode {
  if len(arr) == 0 {
    return nil
  }
  head := &ListNode{Val: arr[0]}
  current := head
  for i := 1; i < len(arr); i++ {
    current.Next = &ListNode{Val: arr[i]}
    current = current.Next
  }
  return head
}

// Helper function to convert linked list to slice for printing
func linkedListToSlice(head *ListNode) []int {
  var result []int
  current := head
  for current != nil {
    result = append(result, current.Val)
    current = current.Next
  }
  return result
}

func main() {
  // Test case 1: [2,4,3] + [5,6,4] = [7,0,8] (342 + 465 = 807)
  l1 := createLinkedList([]int{2, 4, 3})
  l2 := createLinkedList([]int{5, 6, 4})
  result := addTwoNumbers(l1, l2)
  fmt.Println("Test 1:", linkedListToSlice(result))  // [7 0 8]

  // Test case 2: [0] + [0] = [0]
  l1 = createLinkedList([]int{0})
  l2 = createLinkedList([]int{0})
  result = addTwoNumbers(l1, l2)
  fmt.Println("Test 2:", linkedListToSlice(result))  // [0]

  // Test case 3: [9,9,9,9,9,9,9] + [9,9,9,9] = [8,9,9,9,0,0,0,1]
  l1 = createLinkedList([]int{9, 9, 9, 9, 9, 9, 9})
  l2 = createLinkedList([]int{9, 9, 9, 9})
  result = addTwoNumbers(l1, l2)
  fmt.Println("Test 3:", linkedListToSlice(result))  // [8 9 9 9 0 0 0 1]
}

Approach 2: Recursive with Carry

educational

Let the recursion handle the “advance to next digit” logic. At each recursive call, add the current digits plus the carry, extract the new carry, and recursively build the rest of the list.

The base case occurs when both lists are exhausted and the carry is zero.

⏱ Time O(max(m, n)) One pass through lists 💾 Space O(max(m, n)) Call stack + output

Step-by-step Example

Input: l1 = [2, 4, 3], l2 = [5, 6, 4]

The recursion mirrors the iterative solution:

• Call 1: helper(2, 5, 0) → sum=7, digit=7, carry=0 → create node(7) and recurse
• Call 2: helper(4, 6, 0) → sum=10, digit=0, carry=1 → create node(0) and recurse
• Call 3: helper(3, 4, 1) → sum=8, digit=8, carry=0 → create node(8) and recurse
• Call 4: helper(null, null, 0) → base case, return null
• Build result bottom-up: 7 → 0 → 8 → null

The recursion naturally builds the list in the correct order because we construct each node after the recursive call returns.

Pseudocode

function addTwoNumbers(l1, l2):
    return helper(l1, l2, 0)

function helper(l1, l2, carry):
    if not l1 and not l2 and carry == 0:
        return null

    val1 = l1.val if l1 else 0
    val2 = l2.val if l2 else 0

    total = val1 + val2 + carry
    digit = total % 10
    newCarry = total / 10

    nextL1 = l1.next if l1 else null
    nextL2 = l2.next if l2 else null

    nextNode = helper(nextL1, nextL2, newCarry)
    return ListNode(digit, nextNode)

Solution Code

Python

add_two_numbers_recursive.py

from typing import Optional, Tuple


class ListNode:
    def __init__(self, val: int = 0, next: Optional['ListNode'] = None):
        self.val = val
        self.next = next


def addTwoNumbers(l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
    """
    Add two numbers represented by linked lists in reverse order using recursion.

    Time Complexity: O(max(m, n)) where m and n are the lengths of the lists
    Space Complexity: O(max(m, n)) for the recursion call stack and output list
    """

    def helper(l1: Optional[ListNode], l2: Optional[ListNode], carry: int) -> Optional[ListNode]:
        # Base case: both lists are empty and no carry
        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
        digit = total % 10
        new_carry = total // 10

        # Move to next nodes
        next_l1 = l1.next if l1 else None
        next_l2 = l2.next if l2 else None

        # Recursively build the rest of the list
        next_node = helper(next_l1, next_l2, new_carry)

        # Create node with current digit
        return ListNode(digit, next_node)

    return helper(l1, l2, 0)


# Test cases
if __name__ == "__main__":
    # Helper function to create linked list from list
    def create_linked_list(arr):
        if not arr:
            return None
        head = ListNode(arr[0])
        current = head
        for val in arr[1:]:
            current.next = ListNode(val)
            current = current.next
        return head

    # Helper function to convert linked list to list for printing
    def linked_list_to_list(head):
        result = []
        current = head
        while current:
            result.append(current.val)
            current = current.next
        return result

    # Test case 1: [2,4,3] + [5,6,4] = [7,0,8] (342 + 465 = 807)
    l1 = create_linked_list([2, 4, 3])
    l2 = create_linked_list([5, 6, 4])
    result = addTwoNumbers(l1, l2)
    print(f"Test 1: {linked_list_to_list(result)}")  # [7, 0, 8]

    # Test case 2: [0] + [0] = [0]
    l1 = create_linked_list([0])
    l2 = create_linked_list([0])
    result = addTwoNumbers(l1, l2)
    print(f"Test 2: {linked_list_to_list(result)}")  # [0]

    # Test case 3: [9,9,9,9,9,9,9] + [9,9,9,9] = [8,9,9,9,0,0,0,1] (9999999 + 9999 = 10009998)
    l1 = create_linked_list([9, 9, 9, 9, 9, 9, 9])
    l2 = create_linked_list([9, 9, 9, 9])
    result = addTwoNumbers(l1, l2)
    print(f"Test 3: {linked_list_to_list(result)}")  # [8, 9, 9, 9, 0, 0, 0, 1]

C++

add_two_numbers_recursive.cpp

#include <iostream>
#include <vector>

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x = 0) : val(x), next(nullptr) {}
};

ListNode* helper(ListNode* l1, ListNode* l2, int carry) {
    // Base case: both lists are empty and no carry
    if (!l1 && !l2 && carry == 0) {
        return nullptr;
    }

    int val1 = l1 ? l1->val : 0;
    int val2 = l2 ? l2->val : 0;

    int total = val1 + val2 + carry;
    int digit = total % 10;
    int newCarry = total / 10;

    // Move to next nodes
    ListNode* nextL1 = l1 ? l1->next : nullptr;
    ListNode* nextL2 = l2 ? l2->next : nullptr;

    // Recursively build the rest of the list
    ListNode* nextNode = helper(nextL1, nextL2, newCarry);

    // Create node with current digit
    return new ListNode(digit, nextNode);
}

ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
    /*
    Add two numbers represented by linked lists in reverse order using recursion.

    Time Complexity: O(max(m, n)) where m and n are the lengths of the lists
    Space Complexity: O(max(m, n)) for the recursion call stack and output list
    */
    return helper(l1, l2, 0);
}

// Helper function to create linked list from vector
ListNode* createLinkedList(const std::vector<int>& arr) {
    if (arr.empty()) return nullptr;
    ListNode* head = new ListNode(arr[0]);
    ListNode* current = head;
    for (size_t i = 1; i < arr.size(); i++) {
        current->next = new ListNode(arr[i]);
        current = current->next;
    }
    return head;
}

// Helper function to print linked list
void printLinkedList(ListNode* head) {
    std::cout << "[";
    bool first = true;
    while (head) {
        if (!first) std::cout << ", ";
        std::cout << head->val;
        head = head->next;
        first = false;
    }
    std::cout << "]" << std::endl;
}

// Helper function to delete linked list
void deleteLinkedList(ListNode* head) {
    while (head) {
        ListNode* temp = head;
        head = head->next;
        delete temp;
    }
}

int main() {
    // Test case 1: [2,4,3] + [5,6,4] = [7,0,8] (342 + 465 = 807)
    ListNode* l1 = createLinkedList({2, 4, 3});
    ListNode* l2 = createLinkedList({5, 6, 4});
    ListNode* result = addTwoNumbers(l1, l2);
    std::cout << "Test 1: ";
    printLinkedList(result);
    deleteLinkedList(result);

    // Test case 2: [0] + [0] = [0]
    l1 = createLinkedList({0});
    l2 = createLinkedList({0});
    result = addTwoNumbers(l1, l2);
    std::cout << "Test 2: ";
    printLinkedList(result);
    deleteLinkedList(result);

    // Test case 3: [9,9,9,9,9,9,9] + [9,9,9,9] = [8,9,9,9,0,0,0,1]
    l1 = createLinkedList({9, 9, 9, 9, 9, 9, 9});
    l2 = createLinkedList({9, 9, 9, 9});
    result = addTwoNumbers(l1, l2);
    std::cout << "Test 3: ";
    printLinkedList(result);
    deleteLinkedList(result);

    return 0;
}

Java

add_two_numbers_recursive.java

import java.util.ArrayList;
import java.util.List;

class ListNode {
    int val;
    ListNode next;
    ListNode(int x) {
        val = x;
    }
}

public class add_two_numbers_recursive {
    /**
     * Add two numbers represented by linked lists in reverse order using recursion.
     *
     * Time Complexity: O(max(m, n)) where m and n are the lengths of the lists
     * Space Complexity: O(max(m, n)) for the recursion call stack and output list
     */
    public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        return helper(l1, l2, 0);
    }

    private static ListNode helper(ListNode l1, ListNode l2, int carry) {
        // Base case: both lists are empty and no 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;
        int digit = total % 10;
        int newCarry = total / 10;

        // Move to next nodes
        ListNode nextL1 = l1 != null ? l1.next : null;
        ListNode nextL2 = l2 != null ? l2.next : null;

        // Recursively build the rest of the list
        ListNode nextNode = helper(nextL1, nextL2, newCarry);

        // Create node with current digit
        ListNode node = new ListNode(digit);
        node.next = nextNode;
        return node;
    }

    // Helper function to create linked list from array
    private static ListNode createLinkedList(int[] arr) {
        if (arr.length == 0) return null;
        ListNode head = new ListNode(arr[0]);
        ListNode current = head;
        for (int i = 1; i < arr.length; i++) {
            current.next = new ListNode(arr[i]);
            current = current.next;
        }
        return head;
    }

    // Helper function to convert linked list to list for printing
    private static List<Integer> linkedListToList(ListNode head) {
        List<Integer> result = new ArrayList<>();
        ListNode current = head;
        while (current != null) {
            result.add(current.val);
            current = current.next;
        }
        return result;
    }

    public static void main(String[] args) {
        // Test case 1: [2,4,3] + [5,6,4] = [7,0,8] (342 + 465 = 807)
        ListNode l1 = createLinkedList(new int[]{2, 4, 3});
        ListNode l2 = createLinkedList(new int[]{5, 6, 4});
        ListNode result = addTwoNumbers(l1, l2);
        System.out.println("Test 1: " + linkedListToList(result));  // [7, 0, 8]

        // Test case 2: [0] + [0] = [0]
        l1 = createLinkedList(new int[]{0});
        l2 = createLinkedList(new int[]{0});
        result = addTwoNumbers(l1, l2);
        System.out.println("Test 2: " + linkedListToList(result));  // [0]

        // Test case 3: [9,9,9,9,9,9,9] + [9,9,9,9] = [8,9,9,9,0,0,0,1]
        l1 = createLinkedList(new int[]{9, 9, 9, 9, 9, 9, 9});
        l2 = createLinkedList(new int[]{9, 9, 9, 9});
        result = addTwoNumbers(l1, l2);
        System.out.println("Test 3: " + linkedListToList(result));  // [8, 9, 9, 9, 0, 0, 0, 1]
    }
}

JavaScript

add_two_numbers_recursive.js

/**
 * Definition for singly-linked list node.
 */
class ListNode {
    constructor(val = 0, next = null) {
        this.val = val;
        this.next = next;
    }
}

/**
 * Add two numbers represented by linked lists in reverse order using recursion.
 *
 * Time Complexity: O(max(m, n)) where m and n are the lengths of the lists
 * Space Complexity: O(max(m, n)) for the recursion call stack and output list
 *
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
const addTwoNumbers = (l1, l2) => {
    const helper = (l1, l2, carry) => {
        // Base case: both lists are empty and no carry
        if (!l1 && !l2 && carry === 0) {
            return null;
        }

        const val1 = l1 ? l1.val : 0;
        const val2 = l2 ? l2.val : 0;

        const total = val1 + val2 + carry;
        const digit = total % 10;
        const newCarry = Math.floor(total / 10);

        // Move to next nodes
        const nextL1 = l1 ? l1.next : null;
        const nextL2 = l2 ? l2.next : null;

        // Recursively build the rest of the list
        const nextNode = helper(nextL1, nextL2, newCarry);

        // Create node with current digit
        return new ListNode(digit, nextNode);
    };

    return helper(l1, l2, 0);
};

// Helper function to create linked list from array
const createLinkedList = (arr) => {
    if (arr.length === 0) return null;
    const head = new ListNode(arr[0]);
    let current = head;
    for (let i = 1; i < arr.length; i++) {
        current.next = new ListNode(arr[i]);
        current = current.next;
    }
    return head;
};

// Helper function to convert linked list to array for printing
const linkedListToArray = (head) => {
    const result = [];
    let current = head;
    while (current) {
        result.push(current.val);
        current = current.next;
    }
    return result;
};

// Test cases
if (require.main === module) {
    // Test case 1: [2,4,3] + [5,6,4] = [7,0,8] (342 + 465 = 807)
    let l1 = createLinkedList([2, 4, 3]);
    let l2 = createLinkedList([5, 6, 4]);
    let result = addTwoNumbers(l1, l2);
    console.log("Test 1:", linkedListToArray(result));  // [7, 0, 8]

    // Test case 2: [0] + [0] = [0]
    l1 = createLinkedList([0]);
    l2 = createLinkedList([0]);
    result = addTwoNumbers(l1, l2);
    console.log("Test 2:", linkedListToArray(result));  // [0]

    // Test case 3: [9,9,9,9,9,9,9] + [9,9,9,9] = [8,9,9,9,0,0,0,1]
    l1 = createLinkedList([9, 9, 9, 9, 9, 9, 9]);
    l2 = createLinkedList([9, 9, 9, 9]);
    result = addTwoNumbers(l1, l2);
    console.log("Test 3:", linkedListToArray(result));  // [8, 9, 9, 9, 0, 0, 0, 1]
}

module.exports = addTwoNumbers;

Rust

add_two_numbers_recursive.rs

use std::cell::RefCell;
use std::rc::Rc;

#[derive(PartialEq, Eq, Clone, Debug)]
pub struct ListNode {
    pub val: i32,
    pub next: Option<Rc<RefCell<ListNode>>>,
}

impl ListNode {
    #[inline]
    fn new(val: i32) -> Self {
        ListNode { next: None, val }
    }
}

/// Add two numbers represented by linked lists in reverse order using recursion.
///
/// Time Complexity: O(max(m, n)) where m and n are the lengths of the lists
/// Space Complexity: O(max(m, n)) for the recursion call stack and output list
pub fn add_two_numbers(
    l1: Option<Rc<RefCell<ListNode>>>,
    l2: Option<Rc<RefCell<ListNode>>>,
) -> Option<Rc<RefCell<ListNode>>> {
    fn helper(
        l1: Option<Rc<RefCell<ListNode>>>,
        l2: Option<Rc<RefCell<ListNode>>>,
        carry: i32,
    ) -> Option<Rc<RefCell<ListNode>>> {
        // Base case: both lists are empty and no carry
        if l1.is_none() && l2.is_none() && carry == 0 {
            return None;
        }

        let val1 = l1.as_ref().map(|node| node.borrow().val).unwrap_or(0);
        let val2 = l2.as_ref().map(|node| node.borrow().val).unwrap_or(0);

        let total = val1 + val2 + carry;
        let digit = total % 10;
        let new_carry = total / 10;

        // Move to next nodes
        let next_l1 = l1.and_then(|node| node.borrow_mut().next.take());
        let next_l2 = l2.and_then(|node| node.borrow_mut().next.take());

        // Recursively build the rest of the list
        let next_node = helper(next_l1, next_l2, new_carry);

        // Create node with current digit
        Some(Rc::new(RefCell::new(ListNode {
            val: digit,
            next: next_node,
        })))
    }

    helper(l1, l2, 0)
}

// Helper function to create linked list from vector
fn create_linked_list(arr: Vec<i32>) -> Option<Rc<RefCell<ListNode>>> {
    if arr.is_empty() {
        return None;
    }

    let mut head = Rc::new(RefCell::new(ListNode::new(arr[0])));
    let mut current = head.clone();

    for &val in &arr[1..] {
        let new_node = Rc::new(RefCell::new(ListNode::new(val)));
        current.borrow_mut().next = Some(new_node.clone());
        current = new_node;
    }

    Some(head)
}

// Helper function to convert linked list to vector for printing
fn linked_list_to_vec(head: Option<Rc<RefCell<ListNode>>>) -> Vec<i32> {
    let mut result = Vec::new();
    let mut current = head;

    while let Some(node) = current {
        let borrowed = node.borrow();
        result.push(borrowed.val);
        current = borrowed.next.clone();
    }

    result
}

fn main() {
    // Test case 1: [2,4,3] + [5,6,4] = [7,0,8] (342 + 465 = 807)
    let l1 = create_linked_list(vec![2, 4, 3]);
    let l2 = create_linked_list(vec![5, 6, 4]);
    let result = add_two_numbers(l1, l2);
    println!("Test 1: {:?}", linked_list_to_vec(result));  // [7, 0, 8]

    // Test case 2: [0] + [0] = [0]
    let l1 = create_linked_list(vec![0]);
    let l2 = create_linked_list(vec![0]);
    let result = add_two_numbers(l1, l2);
    println!("Test 2: {:?}", linked_list_to_vec(result));  // [0]

    // Test case 3: [9,9,9,9,9,9,9] + [9,9,9,9] = [8,9,9,9,0,0,0,1]
    let l1 = create_linked_list(vec![9, 9, 9, 9, 9, 9, 9]);
    let l2 = create_linked_list(vec![9, 9, 9, 9]);
    let result = add_two_numbers(l1, l2);
    println!("Test 3: {:?}", linked_list_to_vec(result));  // [8, 9, 9, 9, 0, 0, 0, 1]
}

Go

add_two_numbers_recursive.go

package main

import "fmt"

type ListNode struct {
  Val  int
  Next *ListNode
}

/*
 * Add two numbers represented by linked lists in reverse order using recursion.
 *
 * Time Complexity: O(max(m, n)) where m and n are the lengths of the lists
 * Space Complexity: O(max(m, n)) for the recursion call stack and output list
 */
func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
  return helper(l1, l2, 0)
}

func helper(l1 *ListNode, l2 *ListNode, carry int) *ListNode {
  // Base case: both lists are empty and no carry
  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
  digit := total % 10
  newCarry := total / 10

  // Move to next nodes
  var nextL1 *ListNode
  if l1 != nil {
    nextL1 = l1.Next
  }
  var nextL2 *ListNode
  if l2 != nil {
    nextL2 = l2.Next
  }

  // Recursively build the rest of the list
  nextNode := helper(nextL1, nextL2, newCarry)

  // Create node with current digit
  return &ListNode{Val: digit, Next: nextNode}
}

// Helper function to create linked list from array
func createLinkedList(arr []int) *ListNode {
  if len(arr) == 0 {
    return nil
  }
  head := &ListNode{Val: arr[0]}
  current := head
  for i := 1; i < len(arr); i++ {
    current.Next = &ListNode{Val: arr[i]}
    current = current.Next
  }
  return head
}

// Helper function to convert linked list to slice for printing
func linkedListToSlice(head *ListNode) []int {
  var result []int
  current := head
  for current != nil {
    result = append(result, current.Val)
    current = current.Next
  }
  return result
}

func main() {
  // Test case 1: [2,4,3] + [5,6,4] = [7,0,8] (342 + 465 = 807)
  l1 := createLinkedList([]int{2, 4, 3})
  l2 := createLinkedList([]int{5, 6, 4})
  result := addTwoNumbers(l1, l2)
  fmt.Println("Test 1:", linkedListToSlice(result))  // [7 0 8]

  // Test case 2: [0] + [0] = [0]
  l1 = createLinkedList([]int{0})
  l2 = createLinkedList([]int{0})
  result = addTwoNumbers(l1, l2)
  fmt.Println("Test 2:", linkedListToSlice(result))  // [0]

  // Test case 3: [9,9,9,9,9,9,9] + [9,9,9,9] = [8,9,9,9,0,0,0,1]
  l1 = createLinkedList([]int{9, 9, 9, 9, 9, 9, 9})
  l2 = createLinkedList([]int{9, 9, 9, 9})
  result = addTwoNumbers(l1, l2)
  fmt.Println("Test 3:", linkedListToSlice(result))  // [8 9 9 9 0 0 0 1]
}

Approach 3: Space-Optimized Variant

✓ Simple

A third approach demonstrating an alternative technique for solving this problem. This implementation optimizes either time or space complexity compared to the previous approaches.

⏱ Time O(n) Optimized complexity 💾 Space O(1) Efficient space usage

Pseudocode

function approach3():
    // Implementation approach goes here

Solution Code

Python

add_two_numbers_space_optimized.py

"""
Solution for Add Two Numbers
"""

def solve():
    """Implementation for approach 3 of Add Two Numbers"""
    pass

if __name__ == "__main__":
    print("Solution ready")

C++

add_two_numbers_space_optimized.cpp

#include <bits/stdc++.h>
using namespace std;

// Solution for Add Two Numbers
// Approach 3: Implementation

int main() {{
    // Main implementation goes here
    return 0;
}}

Java

AddTwoNumbersSpaceOptimized.java

/**
 * Solution for Add Two Numbers
 * Approach 3
 */
public class AddTwoNumbersSpaceOptimized {{

    public static void main(String[] args) {{
        // Implementation goes here
    }}
}}

JavaScript

add_two_numbers_space_optimized.js

/**
 * Solution for Add Two Numbers
 * Approach 3
 */

function solve() {{
    // Implementation goes here
}}

module.exports = solve;

Rust

add_two_numbers_space_optimized.rs

/// Solution for Add Two Numbers
/// Approach 3

fn main() {{
    println!("Solution implementation");
}}

Go

add_two_numbers_space_optimized.go

package main

import "fmt"

// Solution for Add Two Numbers
// Approach 3

func main() {{
    fmt.Println("Solution implementation")
}}

Common Mistakes

Watch for these pitfalls

• Forgetting to handle the final carry: If two 9s are added, the carry must propagate beyond both lists.
• Treating null as zero: When one list is shorter, you must correctly treat missing nodes as having value 0.
• Losing the carry between iterations: The carry must persist and be added to every step, not reset.
• Incorrect carry extraction: Use integer division (/) for carry and modulo (%) for the digit, not the other way around.
• Creating unnecessary nodes: Only create a new node when you have a digit to store (including the final carry if one exists).

Key Insights

Deeper understanding

• Why reverse order? Storing numbers in reverse order (least significant digit first) is a clever representation that allows O(1) access to each digit as you traverse. In normal order, you’d need to know the list length first.
• The dummy node pattern: A dummy node with value 0 at the start simplifies code by eliminating the special case for the first node. You always append to current.next, never reassign current itself.
• Carry is the key challenge: The hard part is not adding digits—it is ensuring the carry propagates correctly, especially when one list ends before the other or when the final carry needs an extra node.
• Linked list traversal invariant: In both approaches, we maintain the invariant: when either l1 or l2 is null, we treat it as 0. This keeps the logic uniform.

Interview Tips

How to discuss this problem

• Why iterative over recursive? Iterative avoids stack overflow on very long lists (though 100 nodes is safe). It is also faster due to no function call overhead.
• How does reverse order help? Mention that it allows direct digit-by-digit processing without preprocessing. Standard order would require reversing first.
• What about the final carry? Emphasize that the loop condition includes carry so a final carry node is created if needed.
• Edge cases to mention: single-node lists, lists of different lengths, all-9 inputs (to show carry propagation), and zero values.
• Follow-up: Could you solve this if the lists were in normal (non-reversed) order? You’d need to reverse first, or use a stack to process from the tail.

Related Problems

• Add Two Numbers II - Input List is in Forward Order ↗ Medium #445
• Add Binary ↗ Easy #67
• Add Strings ↗ Easy #415
• Add to Array-Form of Integer ↗ Easy #989
• Merge Two Sorted Lists ↗ Easy #21

← Previous
#1 Two Sum Next
#3 Longest Substring Without Repeating Characters →