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 most significant digit first. Neither number has leading zeros, except the number 0 itself.

Return their sum as a linked list in the same form (most significant digit first).

Example 1

Input: l1 = [7,2,4,3], l2 = [5,6,4]
Output: [7,8,0,7]
Explanation: 7243 + 564 = 7807.

Example 2

Input: l1 = [2,4,3], l2 = [5,6,4]
Output: [8,0,7]

Example 3

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

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

Follow-up: Could you solve it without reversing the input lists?

Hints for Add Two Numbers II

1. Hint 1

   Addition starts from the ones digits, which are at the ends of the lists.

2. Hint 2

   Push the digits of each list onto a stack; popping then yields them from least significant to most significant.

3. Hint 3

   Add popped digits with a carry, and build the answer by inserting each new digit at the front of the result list.

How to solve Add Two Numbers II

The digits arrive in the wrong order for column addition, so reverse the reading order with two stacks instead of reversing the lists. Building the result by front insertion turns the least-significant-first sums back into most-significant-first order.

Approach

1. Push every digit of l1 onto stack s1 and every digit of l2 onto s2.
2. Set carry = 0, head = null.
3. While either stack is non-empty or carry is non-zero: sum = carry + pop(s1, or 0) + pop(s2, or 0); create a node with sum % 10 whose next is head, make it the new head; carry = sum / 10.
4. Return head.

Why it works

Popping the stacks walks both numbers from the ones digit upward in lockstep, which is the column method; each new digit is more significant than the ones already built, so prepending it keeps the result most-significant-first, with the final carry ending up in front.

Complexity

• Time — O(m + n)
• Space — O(m + n) for the stacks and the result

Pitfalls

• Converting to built-in integers overflows — up to 100 digits.
• Do not forget the final carry, which becomes a new leading 1.
• Appending at the tail instead of prepending gives the digits backwards.

Reference solution

Python

from typing import Optional

def addTwoNumbers(l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
    s1, s2 = [], []
    while l1:
        s1.append(l1.val)
        l1 = l1.next
    while l2:
        s2.append(l2.val)
        l2 = l2.next
    head = None
    carry = 0
    while s1 or s2 or carry:
        total = carry
        if s1:
            total += s1.pop()
        if s2:
            total += s2.pop()
        head = ListNode(total % 10, head)
        carry = total // 10
    return head

Java

public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    java.util.ArrayDeque<Integer> s1 = new java.util.ArrayDeque<>(), s2 = new java.util.ArrayDeque<>();
    for (; l1 != null; l1 = l1.next) s1.push(l1.val);
    for (; l2 != null; l2 = l2.next) s2.push(l2.val);
    ListNode head = null;
    int carry = 0;
    while (!s1.isEmpty() || !s2.isEmpty() || carry != 0) {
        int sum = carry;
        if (!s1.isEmpty()) sum += s1.pop();
        if (!s2.isEmpty()) sum += s2.pop();
        head = new ListNode(sum % 10, head);
        carry = sum / 10;
    }
    return head;
}

C++

ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
    vector<int> s1, s2;
    for (; l1; l1 = l1->next) s1.push_back(l1->val);
    for (; l2; l2 = l2->next) s2.push_back(l2->val);
    ListNode* head = nullptr;
    int carry = 0;
    while (!s1.empty() || !s2.empty() || carry) {
        int sum = carry;
        if (!s1.empty()) { sum += s1.back(); s1.pop_back(); }
        if (!s2.empty()) { sum += s2.back(); s2.pop_back(); }
        head = new ListNode(sum % 10, head);
        carry = sum / 10;
    }
    return head;
}

JavaScript

var addTwoNumbers = function(l1, l2) {
    var s1 = [], s2 = [];
    for (; l1 !== null; l1 = l1.next) s1.push(l1.val);
    for (; l2 !== null; l2 = l2.next) s2.push(l2.val);
    var head = null, carry = 0;
    while (s1.length > 0 || s2.length > 0 || carry !== 0) {
        var sum = carry;
        if (s1.length > 0) sum += s1.pop();
        if (s2.length > 0) sum += s2.pop();
        head = new ListNode(sum % 10, head);
        carry = Math.floor(sum / 10);
    }
    return head;
};

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 Medium
• Count Special Subsequences Medium