Add Two Numbers

Examples

Input: l1 = [2, 4, 3], l2 = [5, 6, 4]
Output: [7, 0, 8]

342 + 465 = 807, and 807 written least-significant-digit-first is [7, 0, 8].

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

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

99 + 1 = 100, and the carry has to ripple through two extra digits.

Constraints

• Each list has between 1 and 100 nodes.

• 0 <= Node.val <= 9

• Neither list has a leading zero, except the number 0 itself.

Approach

Since each list already represents its number with the smallest digit first, one option is to convert each list into an actual (possibly very large) number, add the two numbers normally, and then turn the result back into a list of digits. This works, but it means building up large number representations and converting between formats, which is more work than the problem actually requires.

The direct approach mirrors how you add numbers by hand: walk both lists at the same time, one digit position at a time, adding the two digits plus any carry left over from the previous position, and writing down the ones digit of that sum while carrying the rest forward. Once both lists are exhausted, if there's still a carry left, it becomes one final extra digit.

Solutions

Brute Force — Convert to Numbers and Back

Read each list into a big integer (using an arbitrary-precision type so very long lists don't lose precision), add the two integers directly, then split the sum's digits back out into a new list, remembering to lay them down least-significant-digit first again.

class ListNode {
  constructor(val, next = null) {
    this.val = val;
    this.next = next;
  }
}

function addTwoNumbers(l1, l2) {
  function listToBigInt(node) {
    let digits = "";
    while (node) {
      digits = String(node.val) + digits; // most significant digit ends up first
      node = node.next;
    }
    return BigInt(digits);
  }

  const sum = listToBigInt(l1) + listToBigInt(l2);
  const digits = sum.toString().split("").reverse(); // back to least-significant-first

  const dummy = new ListNode(0);
  let curr = dummy;
  for (const digit of digits) {
    curr.next = new ListNode(Number(digit));
    curr = curr.next;
  }

  return dummy.next;
}

Time: O(n + m) — but with extra overhead building and parsing big-integer strings · Space: O(n + m)

Optimal — Digit-by-Digit Simulation

Walk both lists at once, one node per position. At each step, add whatever digits are available (treating a list that's already run out as contributing 0) plus the carry from the previous step. The new node's value is that sum modulo 10, and the carry going forward is that sum divided by 10 (rounded down). Keep going as long as either list still has nodes, or there's a leftover carry to place.

class ListNode {
  constructor(val, next = null) {
    this.val = val;
    this.next = next;
  }
}

function addTwoNumbers(l1, l2) {
  const dummy = new ListNode(0);
  let curr = dummy;
  let carry = 0;

  while (l1 !== null || l2 !== null || carry !== 0) {
    const digit1 = l1 ? l1.val : 0;
    const digit2 = l2 ? l2.val : 0;

    const sum = digit1 + digit2 + carry;
    carry = Math.floor(sum / 10);

    curr.next = new ListNode(sum % 10);
    curr = curr.next;

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

  return dummy.next;
}

Time: O(max(n, m)) · Space: O(1) extra, not counting the output list