Add Two Numbers

Medium Problem 57 of 151 Java and Python

Problem

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order (ones digit first), one digit per node.

Add the two numbers and return the sum as a linked list in the same format. The numbers have no leading zeros, except the number 0 itself.

Example 1

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

Example 2

Input: l1 = [9, 9, 9, 9], l2 = [9, 9]
Output: [8, 9, 0, 0, 1]
Why: 9999 + 99 = 10098.

Constraints

1 ≤ number of nodes in each list ≤ 100
0 ≤ Node.val ≤ 9

Explanation

Reversed order is a gift: the lists start at the ones digit, which is exactly where column addition starts.

Add the two digits plus the carry, write sum % 10, carry sum / 10, and keep going while either list or the carry has something left.

Approach 1 · Naive

Convert to big integers

Time O(m + n)
Space O(m + n)

Build each number, add them, and turn the result back into a reversed list. With up to 100 digits you need arbitrary-precision numbers (BigInteger in Java).

Read each list into a number (most significant digit is the last node).
Add them.
Write the digits of the sum, from the ones digit up, into a new list.

Java

import java.math.BigInteger;

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        String sum = toNumber(l1).add(toNumber(l2)).toString();
        ListNode dummy = new ListNode();
        ListNode tail = dummy;
        for (int i = sum.length() - 1; i >= 0; i--) {
            tail.next = new ListNode(sum.charAt(i) - '0');
            tail = tail.next;
        }
        return dummy.next;
    }

    private BigInteger toNumber(ListNode node) {
        StringBuilder digits = new StringBuilder();
        for (; node != null; node = node.next) {
            digits.append(node.val);
        }
        return new BigInteger(digits.reverse().toString());
    }
}

Python

class Solution:
    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        def to_number(node):
            digits = []
            while node:
                digits.append(str(node.val))
                node = node.next
            return int("".join(reversed(digits)))

        total = str(to_number(l1) + to_number(l2))
        dummy = tail = ListNode()
        for digit in reversed(total):
            tail.next = ListNode(int(digit))
            tail = tail.next
        return dummy.next

Approach 2 · Optimal

Digit by digit with a carry

Time O(max(m, n))
Space O(1) besides the output

Walk both lists together, adding digits and the carry, and append each result digit to a new list.

Set carry = 0 and create a dummy head.
While l1, l2 or carry: sum = carry + (l1 digit or 0) + (l2 digit or 0).
Append sum % 10, set carry = sum / 10, advance the lists that are not finished.

Java

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode();
        ListNode 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;
    }
}

Python

class Solution:
    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        dummy = tail = ListNode()
        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

Complexity compared

Approach	Time	Space
Naive Convert to big integers	O(m + n)	O(m + n)
Optimal Digit by digit with a carry	O(max(m, n))	O(1) besides the output

Key takeaways

Keep looping while carry is non-zero, or 5 + 5 returns [0] instead of [0, 1].
Converting to int/long in Java overflows past 18 digits; that is why the digit-by-digit method is the expected answer.

Your notes

Saved in this browser as you type.

Solved it on your own?

Mark it done to track your progress, or star it to come back before an interview.

Next problem