Add Two Numbers II Medium 0 attempts
LeetCode ↗

Add Two Numbers II

Medium Linked List LeetCode

You're given two non-empty linked lists l1 and l2 that each represent a non-negative integer, but this time with the most significant digit stored first. Add the two numbers and return the sum as a linked list in the same most-significant-digit-first order.

Input Format
Implement addTwoNumbersII(l1, l2). Inputs below show JavaScript function arguments; there is no stdin parsing. Linked lists use value arrays. The editor passes nodes with val and next properties; [] becomes null.
Output Format
Return the result described in the statement. Returned list heads are displayed as value arrays; a null head is [].

Sample Input and Output

Example 1 ยท Run Sample

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

Example 2

Input
l1 = [9,9]
l2 = [1]
Output
[1,0,0]
Constraints
  • 1 to 100 nodes per list
  • 0 <= Node.val <= 9
  • Numbers have no leading zeros
Test Cases (2)
Case 1
Args: [[7,2,4,3],[5,6,4]] Expected: [7,8,0,7]
Case 2
Args: [[9,9],[1]] Expected: [1,0,0]
Topics
Linked List

Stack-Based Addition

Use stacks to reverse the digit order, then add with carry.

javascript
function addTwoNumbersII(l1, l2) {
  let s1 = [], s2 = [];
  while (l1) { s1.push(l1.val); l1 = l1.next; }
  while (l2) { s2.push(l2.val); l2 = l2.next; }
  let carry = 0, head = null;
  while (s1.length || s2.length || carry) {
    let sum = carry + (s1.pop() || 0) + (s2.pop() || 0);
    carry = Math.floor(sum / 10);
    let node = {val: sum % 10, next: head};
    head = node;
  }
  return head;
}

Time: O(m + n) | Space: O(m + n)

Saved in this browser only. Private to you.

JavaScript