40. Add Two Numbers

MediumLinked ListsAlso on LeetCode ↗

Two non-negative numbers are stored as linked lists with digits in reverse order (the head is the ones digit). Return their sum as a linked list in the same format.

Example 1

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

Output: [7,0,8]

Explanation: 342 + 465 = 807

Example 2

Input: l1 = [9,9], l2 = [1]

Output: [0,0,1]

Explanation: 99 + 1 = 100

Hint 1

Add digit by digit like on paper, carrying into the next node.

Hint 2

Keep looping while either list or the carry is non-empty.

Linked ListMath

Reference solution for Elementary addition (time O(max(n, m)), space O(1) extra). Each solution passes every test in all four languages.

class Solution:
    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        dummy = tail = ListNode()
        carry = 0
        while l1 or l2 or carry:
            s = carry + (l1.val if l1 else 0) + (l2.val if l2 else 0)
            carry, digit = divmod(s, 10)
            tail.next = ListNode(digit)
            tail = tail.next
            l1 = l1.next if l1 else None
            l2 = l2.next if l2 else None
        return dummy.next

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

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

function addTwoNumbers(l1, l2) {
  const dummy = new ListNode();
  let tail = dummy, carry = 0;
  while (l1 || l2 || carry) {
    const s = carry + (l1 ? l1.val : 0) + (l2 ? l2.val : 0);
    carry = Math.floor(s / 10);
    tail.next = new ListNode(s % 10);
    tail = tail.next;
    l1 = l1 && l1.next;
    l2 = l2 && l2.next;
  }
  return dummy.next;
}

Try solving it yourself first. Interviewers care more about how you explain the approach than about the finished code.

Language

40. Add Two Numbers

Example 1

Example 2

Approach 1: Elementary addition ✅