32. Add Two Numbers

MediumLinked List Math Recursion

Two non-negative integers are stored as linked lists l1 and l2, one decimal digit per node, with the digits in reverse order: the head holds the ones digit, the next node the tens digit, and so on. So [5,1,3] represents 315.

Return their sum as a linked list in the same reversed format.

Neither number has leading zeros, except the number 0 itself, which is the single-node list [0]. The numbers can be far longer than any built-in integer type can hold.

Example 1

Input: l1 = [5,1,3], l2 = [7,9]
Output: [2,1,4]

Explanation: 315 + 97 = 412, stored in reverse as [2,1,4].

Example 2

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

Example 3

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

Explanation: 999 + 1 = 1000: the carry creates a new most-significant digit.

Constraints

Each list has between 1 and 150 nodes
0 <= Node.val <= 9
Neither list has leading zeros, except the number 0 itself

💡 Hint 1

Because the ones digits come first, you can add the lists exactly the way you add numbers on paper, from right to left.

💡 Hint 2

Walk both lists together, adding the two digits plus the carry. The new digit is sum % 10, the carry is sum / 10 rounded down.

💡 Hint 3

Keep going while either list has nodes left or there is a carry, and treat a missing digit as 0.

Try it yourself first ✎

Solutions stick better after a real attempt. Peek when you're ready.

Approach

Simulate grade-school addition. The reversed storage means both lists start at the least significant digit, which is exactly where addition starts. Walk the two lists in step with a carry: at each position add the available digits (a finished list contributes 0) plus the carry, append sum % 10 as a new node, and carry Math.floor(sum / 10). Continue while either list has nodes or the carry is non-zero, so a final carry becomes one extra digit. Never convert the lists to built-in numbers: 150 digits overflow every native integer type.

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

function addTwoNumbers(l1, l2) {
  const dummy = new ListNode(0);
  let tail = dummy;
  let carry = 0;
  while (l1 || l2 || carry) {
    let 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 = Math.floor(sum / 10);
  }
  return dummy.next;
}

class Solution {
    public 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;
    }
}

/**
 * Definition for singly-linked list (provided):
 * function ListNode(val, next) { this.val = val ?? 0; this.next = next ?? null; }
 *
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
function addTwoNumbers(l1, l2) {

}

Ctrl/⌘ + ' run · Ctrl/⌘ + Enter submit