Add Two Numbers

Question

The task is taken from leetcode

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Example:

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)

Output: 7 -> 0 -> 8

Explanation: 342 + 465 = 807.

My solution:

function ListNode(val) {
     this.val = val;
     this.next = null;
}
const numberA3 = new ListNode(3);
const numberA2 = new ListNode(4);
numberA2.next = numberA3;
const numberA1 = new ListNode(2);
numberA1.next = numberA2;

const numberB3 = new ListNode(4);
const numberB2 = new ListNode(6);
numberB2.next = numberB3;
const numberB1 = new ListNode(5);
numberB1.next = numberB2;

var addTwoNumbers = function(l1, l2) {
  let i = l1;
  let j = l2;
  let sum = new ListNode(null, null);
  let rollover = 0;
  let isFirst = true;
  let first, previous;
  const sanitize = x => (x && !isNaN(x.val)) ? x.val : 0;

  while(i || j) {

    let k = sanitize(i) + sanitize(j) + rollover;
    rollover = 0;
    if (k > 9) {
      const tmp = k + '';
      k = Number(tmp[1]);
      rollover = Number(tmp[0]);
    }
    if (!isFirst) { previous = sum; }
    sum = new ListNode(k, new ListNode(k));
    if (!isFirst) { previous.next = sum; }
    if (isFirst) { first = sum; }

    isFirst = false;
    i = i ? i.next : i;
    j = j ? j.next : j;
  }
  if (rollover > 0) {
    previous = sum;
    sum = new ListNode(rollover, new ListNode(rollover));
    previous.next = sum;
  }
  return first;
};

let result = addTwoNumbers(numberA1, numberB1);


while(result) {
  console.log(result.val);
  result = result.next;
}

Answer 1

Wow that is a lot of code to add two numbers.

Potential bug

The function ListNode has one argument yet in the function addTwoNumbers you call it with two arguments. However it does not manifest as a bug as you add the link in the lines following the node creation.

This also results in you creating twice as many nodes as needed.

E.G the second node is dropped and never used.

sum = new ListNode(k, new ListNode(k));

Sanitize

The question states that the inputs are digits so there is no need to sanitize the lists. The only time you vet (arr sanitize) input is when that input comes from the insane, only networks and humans can be insane hence you only sanitize data from them. (Why I hate libraries and frameworks.. Their interfaces face humans (via code) so they are full of vetting code that negatively effect their performance)

i, j and sometime k

Generally the named variables i, j, k are used as indexes. This is so ubiquitous in C syntax like languages that using them for other purposes is a definite no no.

Use numbers

You should never bring a string to a numbers party.

The variable you call rollover is called carry. The carry can be extracted from the sum as carry = sum / 10 | 0 which is a lot faster than converting to a string.

The core of the adder requires 3 numbers a, b, and carry that will give a val and carry and use one intermediate to avoid repeating an operation.

sum = a + b + carry, 
val = sum % 10;
carry = (sum - val) / 10;

// or 
sum = a + b + carry, 
val = sum % 10;
carry = sum / 10 | 0;

Testing

I did not fully test your code as it did not fit well with my linked list lib and my brain not work good this morn I'm a little lazy today. If there are other problems I do not see them in the code.

Rewrite

It is assumed that the linked list functions are not part of the problem to solve. The answer contains some list helpers that can be implemented in a variety of ways.

• Node creates a linked list node the new token.
• Helper function for testing toList converts an array to a list returning the head node as the most significant digit. (Note | 0 to force type Number

Changes

• No sanity check
• Uses numbers rather than string to find carry
• Uses a do while to avoid the extra code needed to handle the final carry (some argue do whiles are too complex for humans to use and should be avoided, all I can say to the down voters, "Du..Really???")

Edge case

The example show an edge case of zero add zero as long lists of zero

The second version check if the result is zero and returns a single node containing 0 which to me seams to more correct answer.

BUT what about 001 + 1 the result is 002 I have not bothered with this edge case (or "leave it for you to solve if interested")

_{^{(hint: hold last node with value)}}

function Node(val, next){ return {val, next, 
   toString() {return "" + (this.next ? this.next : "") + this.val}
}};
const toList = (vals, p) => (vals.forEach(v => p = Node(v | 0, p)), p);
const reverseList = (l, p) => {do{p = Node(l.val ,p) }while(l = l.next); return p};

const A = toList([..."33140613"]), B = toList([..."9283629"]);
const A1 = toList([..."00000"]), B1 = toList([..."00000"]);
const A2 = toList([..."00100"]), B2 = toList([..."900"]);

console.log(A + " + " + B + " = " + add(A, B));
console.log("Wrong: " + A1 + " + " + B1 + " = " + add(A1, B1));
console.log("Wrong ?: " + A2 + " + " + B2 + " = " + add(A2, B2));


function add(nA, nB) {
    var carry = 0, a, b, result;
    do {
        nA ? (a = nA.val, nA = nA.next) : a = 0;
        nB ? (b = nB.val, nB = nB.next) : b = 0;
        const sum = a + b + carry, val = sum % 10;
        carry = (sum - val) / 10;
        result = Node(val, result);
    } while(nA || nB || carry !== 0);
    return reverseList(result);
}

Edge case

Return single node for zero.

function Node(val, next){ return {val, next, 
   toString() {return "" + (this.next ? this.next : "") + this.val}
}};
const toList = (vals, p) => (vals.forEach(v => p = Node(v | 0, p)), p);
const reverseList = (l, p) => {do{p = Node(l.val ,p) }while(l = l.next); return p};


const A = toList([..."33140613"]), B = toList([..."9283629"]);
const A1 = toList([..."00000"]), B1 = toList([..."00000"]);
const A2 = toList([..."00100"]), B2 = toList([..."900"]);

console.log(A + " + " + B + " = " + add(A, B));
console.log(A1 + " + " + B1 + " = " + add(A1, B1));
console.log("Wrong: " + A2 + " + " + B2 + " = " + add(A2, B2));


function add(nA, nB) {
    var carry = 0, a, b, result, hasVal = 0;
    do {
        nA ? (a = nA.val, nA = nA.next) : a = 0;
        nB ? (b = nB.val, nB = nB.next) : b = 0;
        const sum = a + b + carry, val = sum % 10;
        carry = (sum - val) / 10;
        result = Node(val, result);
        hasVal += sum;
    } while(nA || nB || carry !== 0);
    return hasVal ? reverseList(result) : Node(0);
}

_{^{This answer contains subjective opinions that do not reflect the view of the CR community B.M.}}

Answer 2

There are few ways to simplify the code. First, to deal with rollover you don't need to convert a number to string and back.

    if (k > 9) {
        rollover = 1;
        k -= 10;
    }

looks more natural.

Second, the isFirst logic is rather convoluted. A standard technique is to initialize the resulting list with the dummy head, and not worry about the special case anymore. In pseudocode:

    dummy = ListNode()
    tail = dummy
    while (....) {
        compute sum
        tail.next = ListNode(sum)
        tail = tail.next
        advance lists
    }
    handle the remaining rollover
    return dummy.next

Finally, testing for i and j at the end of the loop effectively repeats the test you've already done at the beginning. I recommend to change while (i || j) to while (i && j), and deal with the remaining tail separately (notice that one of the tails is guaranteed to be empty, and one of the last loops is a no-op):

    while (i && j) {
        ....
    }

    while (i) {
        propagate rollover
    }

    while (j) {
        propagate rollover
    }

The last two loops are good candidates to become a function.

Answer 3

I think you're over-complicating the problem -- you need to think of a different approach.

Here's an algorithm: consider the first digit in the linked list. Add it to the "running total." If there's another number in the list, multiply it by 10*(number count) and add it to the running total. Keep going until you run out of new numbers.

Think of it this way for an input of 8->3->4:

1) Set runningTotal to 8 initially.
2) There's another item in the list; multiply 3 by 10*1 to get 30. Add to running total. New running total: 38.
3) There's another item in the list; multiply 4 by 10*2 to get 400. Add to running total. New running total: 483.

And so on. This works for lists of any size.

Make a function that will convert a linked list to an integer as described as above, and then you just need to add up the results for both lists.