Add Two Numbers

---

Add Two Numbers: 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.

---

Try this Problem on your own or check similar problems:

1. Add Two Numbers II
2. Add Strings

Solution:

Java

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    ListNode dummy = new ListNode(0);
    ListNode iter = dummy;
    int carry = 0;

    while (l1 != null || l2 != null || carry != 0) {
        int val1 = (l1 != null) ? l1.val : 0;
        int val2 = (l2 != null) ? l2.val : 0;
        int sum = carry + val1 + val2;

        carry = sum / 10;
        iter.next = new ListNode(sum % 10);
        iter = iter.next;

        if (l1 != null)
            l1 = l1.next;
        if (l2 != null)
            l2 = l2.next;
    }

    return dummy.next;
}

JavaScript

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
var addTwoNumbers = function (l1, l2) {
  let dummy = new ListNode(0);
  let iter = dummy;
  let carry = 0;

  while (l1 || l2 || carry !== 0) {
    let val1 = l1 ? l1.val : 0;
    let val2 = l2 ? l2.val : 0;
    let sum = carry + val1 + val2;

    carry = Math.floor(sum / 10);
    iter.next = new ListNode(sum % 10);
    iter = iter.next;

    if (l1) {
      l1 = l1.next;
    }
    if (l2) {
      l2 = l2.next;
    }
  }

  return dummy.next;
};

Python

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        dummy = ListNode(0)
        iter = dummy
        carry = 0

        while l1 or l2 or carry != 0:
            val1 = l1.val if l1 else 0
            val2 = l2.val if l2 else 0
            sum = carry + val1 + val2

            carry = sum // 10
            iter.next = ListNode(sum % 10)
            iter = iter.next

            if l1:
                l1 = l1.next
            if l2:
                l2 = l2.next

        return dummy.next

C++

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode* dummy = new ListNode(0);
        ListNode* iter = dummy;
        int carry = 0;

        while (l1 || l2 || carry != 0) {
            int val1 = l1 ? l1->val : 0;
            int val2 = l2 ? l2->val : 0;
            int sum = carry + val1 + val2;

            carry = sum / 10;
            iter->next = new ListNode(sum % 10);
            iter = iter->next;

            if (l1) {
                l1 = l1->next;
            }
            if (l2) {
                l2 = l2->next;
            }
        }

        return dummy->next;
    }
};

---

Time/Space Complexity:

• Time Complexity: O(max(m,n)) where m and n are respectively lengths of list l1 and l2
• Space Complexity: O(max(m,n))

---

Explanation:

As always when we're dealing with linked list problems it's useful to define dummy pointer and iterator pointing to the dummy head which we will use to iterate over the newly created list. We keep on adding nodes on the result linked list until we're out of elements from both linked lists given as inputs and carry (which we calculate each iteration, and which is 1 if the sum of digits is greater than 9). l1 and l2 help us to iterate over linked lists given as input. dummy.next will be pointing to the head of result so we return it as our solution. The time and space complexity are proportional to the number of nodes we have in the larger list (since we have or statement in the loop).