sum_lists_original.md

NOTE: This was taken from Cracking the Coding Interview 6th Edition.

Prompt

You have two numbers represented by a linked list, where each node contains a single digit. The digits are stored in reverse order, such that the 1's digit is at the head of the list. Write a function that adds the two numbers and returns the sum as a linked list.

Example

Input: (7 -> 1 -> 6) + (5 -> 9 -> 2). That is, 617 + 295. Output: (2 -> 1 -> 9). That is, 912.

Solution

Repl

We can mimic the addition process of adding 2 values in the lowest range and carrying the 1 recursively by adding node by node, carrying over 'excess' to the next node. Walking through for the linked list above:

1. 7 + 5 give us 12, so 2 becomes the first node of the new linked list & we carry the 1 to the next sum. List: 2 -> ?
2. 1 + 9 give us 10, and the carry gives us 11. 1 becomes the second node, and we carry the 1 to the next sum. List: 2 -> 1 -> ?
3. 6 + 2 give us 8, and the carry gives us 9. 9 becomes the 3rd node. List: 2 -> 1 -> 9

Solution Code

function Node(val, next) {
  this.val = val;
  this.next = next || null;
}

function addLists(n1, n2, carry = 0) {
  if (n1 === null && n2 === null && carry === 0) return null;
  if (n1 !== null) carry += n1.val;
  if (n2 !== null) carry += n2.val;
  var node = new Node(carry % 10);
  
  if (n1 !== null || n2 !== null) {
    let nextDigit = addLists(n1 === null ? null : n1.next, n2 === null ? null : n2.next, carry >= 10 ? 1 : 0);
    node.next = nextDigit;
  }
  return node;
}

When writing the solution - the edge case to consider is when one list is shorter than the other. We want to avoid a null pointer exception.