Add Two Numbers

MediumLinked List Math Recursion

An arbitrary-precision math library stores huge non-negative integers as singly linked lists of decimal digits, least significant digit first: the head holds the ones digit, the next node the tens digit, and so on. The number 4096 is stored as [6,9,0,4].

Given two such numbers, l1 and l2, return their sum as a linked list in the same format.

Neither input has leading zeros, except the number zero itself, which is the single node [0]. The numbers can be far too long for any built-in integer type.

Example 1

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

Explanation: 4096 + 34 = 4130, stored ones digit first.

Example 2

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

Explanation: 0 + 27 = 27: adding zero leaves the other number unchanged.

Example 3

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

Explanation: 95 + 5 = 100: the carry ripples through both digits and creates a new one.

Constraints

Each list has between 1 and 150 nodes.
Every node holds a single digit from 0 to 9.
Neither number 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