Problem statement

Two non-negative integers are stored in two non-empty singly linked lists, l1 and l2, one decimal digit per node, with the digits in reverse order — the head holds the ones digit. Neither number has leading zeros, except the number 0 itself.

Return their sum as a linked list in the same reversed-digit form.

Example 1

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

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]
Explanation: 9999999 + 9999 = 10009998; the final carry adds a new node.

Constraints

• The number of nodes in each list is in the range [1, 100]
• 0 <= Node.val <= 9
• Neither number has leading zeros, except the number 0 itself

Hints for Add Two Numbers

1. Hint 1

   The heads are the ones digits, so the lists are already in the order grade-school addition works in.

2. Hint 2

   Walk both lists together, adding the two digits and the carry; the new digit is sum % 10 and the new carry sum / 10.

3. Hint 3

   Keep going while either list has nodes or the carry is non-zero — the last carry can create one extra node.

How to solve Add Two Numbers

Reversed digits mean the least significant digits come first, which is exactly the order column addition proceeds in. One simultaneous walk of both lists, with a carry, produces the answer digit by digit.

Approach

1. Create a dummy node and a tail pointer; set carry = 0.
2. While l1, l2 or carry is non-zero: sum = carry + (l1 ? l1.val : 0) + (l2 ? l2.val : 0).
3. Append a node with sum % 10, set carry = sum / 10, and advance whichever lists are not exhausted.
4. Return dummy.next.

Why it works

This is the column method: each output digit is the sum of the two digits in that column plus the carry from the column to its right, and the carry is always 0 or 1. Treating a finished list as contributing 0s handles numbers of different lengths.

Complexity

• Time — O(max(m, n))
• Space — O(max(m, n)) for the result list

Pitfalls

• Converting the lists to built-in integers overflows — a number can have 100 digits.
• Forgetting the final carry loses the leading 1 (e.g. 5 + 5 = 10).
• The lists can have different lengths; keep reading the longer one after the shorter one ends.

Reference solution

Python

from typing import Optional

def addTwoNumbers(l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
    dummy = ListNode(0)
    tail = dummy
    carry = 0
    while l1 or l2 or carry:
        total = carry
        if l1:
            total += l1.val
            l1 = l1.next
        if l2:
            total += l2.val
            l2 = l2.next
        tail.next = ListNode(total % 10)
        tail = tail.next
        carry = total // 10
    return dummy.next

Java

public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    ListNode dummy = new ListNode(0), tail = dummy;
    int carry = 0;
    while (l1 != null || l2 != null || carry != 0) {
        int sum = carry;
        if (l1 != null) { sum += l1.val; l1 = l1.next; }
        if (l2 != null) { sum += l2.val; l2 = l2.next; }
        tail.next = new ListNode(sum % 10);
        tail = tail.next;
        carry = sum / 10;
    }
    return dummy.next;
}

C++

ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
    ListNode dummy(0);
    ListNode* tail = &dummy;
    int carry = 0;
    while (l1 || l2 || carry) {
        int sum = carry;
        if (l1) { sum += l1->val; l1 = l1->next; }
        if (l2) { sum += l2->val; l2 = l2->next; }
        tail->next = new ListNode(sum % 10);
        tail = tail->next;
        carry = sum / 10;
    }
    return dummy.next;
}

JavaScript

var addTwoNumbers = function(l1, l2) {
    var dummy = new ListNode(0), tail = dummy, carry = 0;
    while (l1 !== null || l2 !== null || carry !== 0) {
        var sum = carry;
        if (l1 !== null) { sum += l1.val; l1 = l1.next; }
        if (l2 !== null) { sum += l2.val; l2 = l2.next; }
        tail.next = new ListNode(sum % 10);
        tail = tail.next;
        carry = Math.floor(sum / 10);
    }
    return dummy.next;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More math problems

• Product of the Last K Numbers Medium
• Add 1 to a Number Represented as Linked List Medium
• Double a Number Represented as a Linked List Medium
• Insert Greatest Common Divisors in Linked List Medium
• Add Two Numbers II Medium
• Count Special Subsequences Medium