Talentd
For employersSign in
JobsInternshipsPracticeResume toolsCompaniesArticles
For employers
FleetCode
Make and follow sheets.Sign in

Add Two Numbers solution and explanation

MediumLinked ListMathRecursion6 min read49.3% acceptanceUpdated 9 Apr 2026
Asked atMetaOlaJane StreetEarninBloombergAdobe
+14 moreWixGoogleAmazonMicrosoftAirbnbPalo Alto NetworksAvitoAqr Capital ManagementTCSInfosysIBMZohoCiscoBytedance
Practise Add Two Numbers
9:33
Add Two Numbers - Leetcode 2 - PythonNeetCode · 9:33 · 371K viewsWatch on YouTube
9 more videos on this problem
  1. Add Two Numbers - Leetcode 2 - PythonNeetCode · 9:33 · 371K views
  2. L5. Add 2 numbers in LinkedList | Dummy Node Approachtake U forward · 14:48 · 312K views
  3. LeetCode Add Two Numbers Solution Explained - JavaNick White · 6:23 · 151K views
  4. Leetcode 2. Add Two Numbers | Add digits of two linked lists and return their sum | Linked ListCode with Alisha · 11:32 · 129K views
  5. Add Two Numbers (LeetCode 2) | Full solution with diagrams | EASIEST EVER | Study AlgorithmsNikhil Lohia · 13:18 · 119K views
  6. LeetCode 2: Add Two Numbers Solution in Python (Linked List Explained)CodingNinja · 8:04 · 55K views
  7. LeetCode 2: Add Two NumbersAbstracted Away · 6:10 · 23K views
  8. Add Two Numbers | Live Coding with Explanation | Leetcode - 2Algorithms Made Easy · 4:02 · 21K views
  9. Add Two Numbers Python Solution - LeetCode #2Professor Oakes · 6:48 · 20K views
  10. LEETCODE 2 (JAVASCRIPT) | ADD TWO NUMBERSAndy Gala · 23:00 · 8K views

The problem

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.

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]

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.

Approach overview

Problem Overview: Two non-empty linked lists represent two non‑negative integers. Each node stores a single digit, and digits are stored in reverse order. You add the two numbers and return the sum as a new linked list while correctly handling digit carry.

Approach 1: Iterative Linked List Addition (O(n) time, O(1) extra space)

Traverse both lists simultaneously while maintaining a carry value. At each step, read the current digit from each list (use 0 if a list is exhausted), compute sum = x + y + carry, store sum % 10 as the new node, and update carry = sum // 10. Move both pointers forward and append the new node to the result list. This works because digits are already stored in reverse order, so addition proceeds exactly like manual column addition from least significant digit to most.

The loop continues while either list still has nodes or a carry remains. A dummy head node simplifies result construction and avoids special handling for the first node. Time complexity is O(max(m,n)) because each node is processed once, and extra space is O(1) excluding the output list. This approach relies heavily on pointer manipulation in a linked list and basic math operations for carry propagation.

Approach 2: Recursive Digit Addition (O(n) time, O(n) space)

The same addition logic can be expressed recursively. Each recursive call processes one pair of nodes and returns the resulting node for that digit. Compute the digit sum and carry exactly as in the iterative method, create a node with sum % 10, and recursively compute the next node using the remaining list nodes and updated carry.

The recursion stops when both lists are exhausted and no carry remains. If a carry still exists after the final digits, create one last node to store it. Time complexity remains O(max(m,n)) since each digit is processed once. Space complexity becomes O(n) due to the call stack used by recursion. This version is concise and elegant but less memory‑efficient than the iterative solution.

Recommended for interviews: The iterative approach is what most interviewers expect. It demonstrates comfort with linked list traversal, pointer manipulation, and carry management. Explaining the recursive version afterward shows deeper understanding of the same logic expressed through recursion. Implementing the iterative solution correctly without edge‑case bugs (different list lengths, leftover carry) is usually the key evaluation point.

Approach 1: Iterative Approach

This approach involves iterating through both linked lists, node by node, adding corresponding values along with any carry from the previous addition. The result at each step is appended to a new linked list. If one list is longer than the other, the iteration continues on the longer list alone. A final check is done to handle any remaining carry.

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        dummy = ListNode()
        current = dummy
        carry = 0
        while l1 or l2:
            x = l1.val if l1 else 0
            y = l2.val if l2 else 0
            sum = carry + x + y
            carry = sum // 10
            current.next = ListNode(sum % 10)
            current = current.next
            if l1: l1 = l1.next
            if l2: l2 = l2.next
        if carry > 0:
            current.next = ListNode(carry)
        return dummy.next
public class ListNode {
    int val;
    ListNode next;
    ListNode(int val) { this.val = val; }
}

public class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0);
        ListNode current = dummy;
        int carry = 0;
        while (l1 != null || l2 != null) {
            int x = (l1 != null) ? l1.val : 0;
            int y = (l2 != null) ? l2.val : 0;
            int sum = carry + x + y;
            carry = sum / 10;
            current.next = new ListNode(sum % 10);
            current = current.next;
            if (l1 != null) l1 = l1.next;
            if (l2 != null) l2 = l2.next;
        }
        if (carry > 0) {
            current.next = new ListNode(carry);
        }
        return dummy.next;
    }
}
#include <iostream>
using namespace std;

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode dummy(0);
        ListNode* current = &dummy;
        int carry = 0;
        while (l1 != nullptr || l2 != nullptr) {
            int x = (l1 != nullptr) ? l1->val : 0;
            int y = (l2 != nullptr) ? l2->val : 0;
            int sum = carry + x + y;
            carry = sum / 10;
            current->next = new ListNode(sum % 10);
            current = current->next;
            if (l1 != nullptr) l1 = l1->next;
            if (l2 != nullptr) l2 = l2->next;
        }
        if (carry > 0) {
            current->next = new ListNode(carry);
        }
        return dummy.next;
    }
};
function ListNode(val, next) {
    this.val = (val===undefined ? 0 : val)
    this.next = (next===undefined ? null : next)
}

var addTwoNumbers = function(l1, l2) {
    let dummy = new ListNode(0);
    let current = dummy;
    let carry = 0;
    while (l1 !== null || l2 !== null) {
        let x = (l1 !== null) ? l1.val : 0;
        let y = (l2 !== null) ? l2.val : 0;
        let sum = carry + x + y;
        carry = Math.floor(sum / 10);
        current.next = new ListNode(sum % 10);
        current = current.next;
        if (l1 !== null) l1 = l1.next;
        if (l2 !== null) l2 = l2.next;
    }
    if (carry > 0) {
        current.next = new ListNode(carry);
    }
    return dummy.next;
};
#include <stdlib.h>

struct ListNode {
    int val;
    struct ListNode *next;
};

struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2) {
    struct ListNode dummy;
    struct ListNode* current = &dummy;
    int carry = 0;
    
    while (l1 != NULL || l2 != NULL) {
        int x = (l1 != NULL) ? l1->val : 0;
        int y = (l2 != NULL) ? l2->val : 0;
        int sum = carry + x + y;
        carry = sum / 10;
        current->next = (struct ListNode*)malloc(sizeof(struct ListNode));
        current = current->next;
        current->val = sum % 10;
        current->next = NULL;
        
        if (l1 != NULL) l1 = l1->next;
        if (l2 != NULL) l2 = l2->next;
    }
    
    if (carry > 0) {
        current->next = (struct ListNode*)malloc(sizeof(struct ListNode));
        current = current->next;
        current->val = carry;
        current->next = NULL;
    }
    
    return dummy.next;
}
public class ListNode {
    public int val;
    public ListNode next;
    public ListNode(int val=0, ListNode next=null) {
        this.val = val;
        this.next = next;
    }
}

public class Solution {
    public ListNode AddTwoNumbers(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0);
        ListNode current = dummy;
        int carry = 0;
        while (l1 != null || l2 != null) {
            int x = (l1 != null) ? l1.val : 0;
            int y = (l2 != null) ? l2.val : 0;
            int sum = carry + x + y;
            carry = sum / 10;
            current.next = new ListNode(sum % 10);
            current = current.next;
            if (l1 != null) l1 = l1.next;
            if (l2 != null) l2 = l2.next;
        }
        if (carry > 0) {
            current.next = new ListNode(carry);
        }
        return dummy.next;
    }
}

Python uses an iterative approach with a dummy head to simplify list handling. Carries are calculated and updated with each node of the result as lists are traversed until finished.

Complexity

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

Try this approach in the editor

Approach 2: Recursive Approach

The recursive approach solves the problem by recursing down the linked lists, accumulating values with carry and constructing the result linked list from the returned values from child calls. Each recursive call processes one pair of nodes from the lists, similar to how you would process each position in a sum independently in the iterative version.

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        def addTwoNumbersRecursive(l1, l2, carry):
            if not l1 and not l2 and carry == 0:
                return None
            sum_val = carry
            if l1:
                sum_val += l1.val
            if l2:
                sum_val += l2.val
            carry = sum_val // 10
            result = ListNode(sum_val % 10)
            result.next = addTwoNumbersRecursive(l1.next if l1 else None, l2.next if l2 else None, carry)
            return result
        return addTwoNumbersRecursive(l1, l2, 0)
public class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}

public class Solution {
    public ListNode addTwoNumbers(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 sum = carry;
        if (l1 != null) sum += l1.val;
        if (l2 != null) sum += l2.val;
        ListNode result = new ListNode(sum % 10);
        result.next = addTwoNumbersRecursive(l1 != null ? l1.next : null, l2 != null ? l2.next : null, sum / 10);
        return result;
    }
}
#include <iostream>

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

class Solution {
public:
    ListNode* addTwoNumbers(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 sum = carry;
        if (l1 != NULL) sum += l1->val;
        if (l2 != NULL) sum += l2->val;
        ListNode* result = new ListNode(sum % 10);
        result->next = addTwoNumbersRecursive(l1 ? l1->next : NULL, l2 ? l2->next : NULL, sum / 10);
        return result;
    }
};
function ListNode(val, next) {
    this.val = (val===undefined ? 0 : val)
    this.next = (next===undefined ? null : next)
}

var addTwoNumbers = function(l1, l2) {
    return addTwoNumbersRecursive(l1, l2, 0);

    function addTwoNumbersRecursive(l1, l2, carry) {
        if (l1 === null && l2 === null && carry === 0) {
            return null;
        }
        let sum = carry;
        if (l1 !== null) sum += l1.val;
        if (l2 !== null) sum += l2.val;
        let result = new ListNode(sum % 10);
        result.next = addTwoNumbersRecursive(l1 ? l1.next : null, l2 ? l2.next : null, Math.floor(sum / 10));
        return result;
    }
};
#include <stdlib.h>

struct ListNode {
    int val;
    struct ListNode *next;
};

struct ListNode* addTwoNumbersRecursive(struct ListNode* l1, struct ListNode* l2, int carry) {
    if (l1 == NULL && l2 == NULL && carry == 0) {
        return NULL;
    }
    struct ListNode* result = (struct ListNode*)malloc(sizeof(struct ListNode));
    int sum = carry;
    if (l1 != NULL) sum += l1->val;
    if (l2 != NULL) sum += l2->val;
    result->val = sum % 10;
    carry = sum / 10;
    result->next = addTwoNumbersRecursive(l1 ? l1->next : NULL, l2 ? l2->next : NULL, carry);
    return result;
}

struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2) {
    return addTwoNumbersRecursive(l1, l2, 0);
}
public class ListNode {
    public int val;
    public ListNode next;
    public ListNode(int val=0, ListNode next=null) {
        this.val = val;
        this.next = next;
    }
}

public class Solution {
    public ListNode AddTwoNumbers(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 sum = carry;
        if (l1 != null) sum += l1.val;
        if (l2 != null) sum += l2.val;
        ListNode result = new ListNode(sum % 10);
        result.next = AddTwoNumbersRecursive(l1 != null ? l1.next : null, l2 != null ? l2.next : null, sum / 10);
        return result;
    }
}

Python uses a nested function, addTwoNumbersRecursive, that handles node values recursively while maintaining carry, constructing result nodes recursively moving along the lists until no longer needed.

Complexity

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

Try this approach in the editor

Approach 3: Simulation

We traverse two linked lists l_1 and l_2 at the same time, and use the variable carry to indicate whether there is a carry.

Each time we traverse, we take out the current bit of the corresponding linked list, calculate the sum with the carry carry, and then update the value of the carry. Then we add the current bit to the answer linked list. If both linked lists are traversed, and the carry is 0, the traversal ends.

Finally, we return the head node of the answer linked list.

The time complexity is O(max (m, n)), where m and n are the lengths of the two linked lists. We need to traverse the entire position of the two linked lists, and each position only needs O(1) time. Ignoring the space consumption of the answer, the space complexity is O(1).

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */

function addTwoNumbers(l1: ListNode | null, l2: ListNode | null): ListNode | null {
    const dummy = new ListNode();
    let cur = dummy;
    let sum = 0;
    while (l1 != null || l2 != null || sum !== 0) {
        if (l1 != null) {
            sum += l1.val;
            l1 = l1.next;
        }
        if (l2 != null) {
            sum += l2.val;
            l2 = l2.next;
        }
        cur.next = new ListNode(sum % 10);
        cur = cur.next;
        sum = Math.floor(sum / 10);
    }
    return dummy.next;
}
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
	dummy := &ListNode{}
	carry := 0
	cur := dummy
	for l1 != nil || l2 != nil || carry != 0 {
		s := carry
		if l1 != nil {
			s += l1.Val
		}
		if l2 != nil {
			s += l2.Val
		}
		carry = s / 10
		cur.Next = &ListNode{s % 10, nil}
		cur = cur.Next
		if l1 != nil {
			l1 = l1.Next
		}
		if l2 != nil {
			l2 = l2.Next
		}
	}
	return dummy.Next
}
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public var val: Int
 *     public var next: ListNode?
 *     public init() { self.val = 0; self.next = nil; }
 *     public init(_ val: Int) { self.val = val; self.next = nil; }
 *     public init(_ val: Int, _ next: ListNode?) { self.val = val; self.next = next; }
 * }
 */
class Solution {
    func addTwoNumbers(_ l1: ListNode?, _ l2: ListNode?) -> ListNode? {
        var dummy = ListNode.init()
        var carry = 0
        var l1 = l1
        var l2 = l2
        var cur = dummy
        while l1 != nil || l2 != nil || carry != 0 {
            let s = (l1?.val ?? 0) + (l2?.val ?? 0) + carry
            carry = s / 10
            cur.next = ListNode.init(s % 10)
            cur = cur.next!
            l1 = l1?.next
            l2 = l2?.next
        }
        return dummy.next
    }
}
// Definition for singly-linked list.
// #[derive(PartialEq, Eq, Clone, Debug)]
// pub struct ListNode {
//   pub val: i32,
//   pub next: Option<Box<ListNode>>
// }
//
// impl ListNode {
//   #[inline]
//   fn new(val: i32) -> Self {
//     ListNode {
//       next: None,
//       val
//     }
//   }
// }
impl Solution {
    pub fn add_two_numbers(
        mut l1: Option<Box<ListNode>>,
        mut l2: Option<Box<ListNode>>,
    ) -> Option<Box<ListNode>> {
        let mut dummy = Some(Box::new(ListNode::new(0)));
        let mut cur = &mut dummy;
        let mut sum = 0;
        while l1.is_some() || l2.is_some() || sum != 0 {
            if let Some(node) = l1 {
                sum += node.val;
                l1 = node.next;
            }
            if let Some(node) = l2 {
                sum += node.val;
                l2 = node.next;
            }
            cur.as_mut().unwrap().next = Some(Box::new(ListNode::new(sum % 10)));
            cur = &mut cur.as_mut().unwrap().next;
            sum /= 10;
        }
        dummy.unwrap().next.take()
    }
}
# Definition for singly-linked list.
# class ListNode
#     attr_accessor :val, :next
#     def initialize(val = 0, _next = nil)
#         @val = val
#         @next = _next
#     end
# end
# @param {ListNode} l1
# @param {ListNode} l2
# @return {ListNode}
def add_two_numbers(l1, l2)
    dummy = ListNode.new()
    carry = 0
    cur = dummy
    while !l1.nil? || !l2.nil? || carry > 0
        s = (l1.nil? ? 0 : l1.val) + (l2.nil? ? 0 : l2.val) + carry
        carry = s / 10
        cur.next = ListNode.new(s % 10)
        cur = cur.next
        l1 = l1.nil? ? l1 : l1.next
        l2 = l2.nil? ? l2 : l2.next
    end
    dummy.next
end
/**
 * Definition for a singly-linked list.
 * class ListNode {
 *     public $val = 0;
 *     public $next = null;
 *     function __construct($val = 0, $next = null) {
 *         $this->val = $val;
 *         $this->next = $next;
 *     }
 * }
 */
class Solution {
    /**
     * @param ListNode $l1
     * @param ListNode $l2
     * @return ListNode
     */
    function addTwoNumbers($l1, $l2) {
        $dummy = new ListNode(0);
        $current = $dummy;
        $carry = 0;

        while ($l1 !== null || $l2 !== null) {
            $x = $l1 !== null ? $l1->val : 0;
            $y = $l2 !== null ? $l2->val : 0;

            $sum = $x + $y + $carry;
            $carry = (int) ($sum / 10);
            $current->next = new ListNode($sum % 10);
            $current = $current->next;

            if ($l1 !== null) {
                $l1 = $l1->next;
            }

            if ($l2 !== null) {
                $l2 = $l2->next;
            }
        }

        if ($carry > 0) {
            $current->next = new ListNode($carry);
        }

        return $dummy->next;
    }
}
#[
    # Driver code in the solution file
    # Definition for singly-linked list.
    type
    Node[int] = ref object
        value: int
        next: Node[int]

    SinglyLinkedList[T] = object
        head, tail: Node[T]
]#

# More efficient code churning ...
proc addTwoNumbers(l1: var SinglyLinkedList, l2: var SinglyLinkedList): SinglyLinkedList[int] =
  var
    aggregate: SinglyLinkedList
    psum: seq[char]
    temp_la, temp_lb: seq[int]

  while not l1.head.isNil:
    temp_la.add(l1.head.value)
    l1.head = l1.head.next

  while not l2.head.isNil:
    temp_lb.add(l2.head.value)
    l2.head = l2.head.next

  psum = reversed($(reversed(temp_la).join("").parseInt() + reversed(temp_lb).join("").parseInt()))
  for i in psum: aggregate.append(($i).parseInt())

  result = aggregate
Try this approach in the editor

Complexity comparison

ApproachComplexity
Iterative Approach

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

Recursive Approach

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

Simulation–

Complexity analysis

ApproachTimeSpaceWhen to Use
Iterative Linked List AdditionO(max(m,n))O(1) extraStandard interview solution; best when you want minimal memory overhead
Recursive Digit AdditionO(max(m,n))O(n)Useful when recursion is preferred for cleaner code or conceptual clarity

Frequently asked questions

Is Add Two Numbers easy or hard?

Add Two Numbers is generally classified as a Medium difficulty problem. The main challenge is correctly handling different list lengths and carry propagation while constructing the result linked list.

Add Two Numbers Python/Java solution

In Python or Java, the solution typically uses a loop that iterates through both linked lists while tracking a carry variable. A dummy head node is used to simplify result construction, and new nodes are appended as each digit of the sum is calculated.

How to solve Add Two Numbers in O(n)?

Traverse both linked lists simultaneously and maintain a carry variable. At each step compute sum = digit1 + digit2 + carry, store sum % 10 as the new node, and update carry = sum // 10. Continue until both lists are exhausted and no carry remains, giving an O(n) solution where n is the longer list length.

What is the best approach for Add Two Numbers?

The standard solution uses iterative traversal of both linked lists while maintaining a carry value. Each step adds corresponding digits and stores the result digit in a new node. This approach runs in O(n) time and O(1) extra space, making it the most efficient and the most commonly expected answer in coding interviews.

Is Add Two Numbers asked at Google/Amazon/Meta?

Add Two Numbers is a classic linked list problem frequently reported in interviews at companies like Amazon, Google, Meta, and Microsoft. It tests pointer manipulation, carry handling, and understanding of linked list traversal.

What data structure is used in Add Two Numbers?

The core data structure is a singly linked list where each node stores a single digit. The algorithm traverses the lists node by node while constructing a new result linked list. Basic arithmetic operations are used to manage the carry between digits.

What is the time complexity of Add Two Numbers?

The time complexity is O(max(m,n)), where m and n are the lengths of the two linked lists. Each node from both lists is visited once to compute the digit sum and carry. Space complexity is O(1) for the iterative approach, excluding the output list.

Comments

Next problem · similarMultiply StringsMedium
Now write it yourselfClose this page and solve Add Two Numbers in the editor, without looking.
Practise Add Two Numbers