JavaScript Adding two linkedlist values with recursion

Question

I have the following code and spent 6 hours trying to solve without luck. It gets stuck with LinkedList of 1 -> 8, 0 -> null as the input. My output is just 1 -> null and I'm not sure why. I tried to follow through my code manually and it should create new "next = {val: 8, next: null}", but it isn't happening...

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */


const traversal = function(l1, l2, s, n) {
    if (l1 !== null && l2 !== null) {
        n.val = l1.val + l2.val + s;
    } else if (l1 !== null && l2 === null && !s) {
        n.val = l1.val + s;
    } else if (l1 === null && l2 !== null && !s) {
        n.val = l2.val + s;
    } else if (l1 === null && l2 === null && s) {
        n.val = s
    }
    s = 0;
    if (n.val > 9) {
        s = Number(n.val.toString()[0])
        n.val = Number(n.val.toString()[1])
    }
    if (l1 === null && l2 === null && !s) {
        return;
    }
    if (l1 !== null && l2 !== null && l1.next && l2.next) {
        n.next = new ListNode
        traversal(l1.next, l2.next, s, n.next)
    } else if (l1 !== null && l2 === null && l1.next !== null && l2.next === null) {
        n.next = new ListNode
        traversal(l1.next, null, s, n.next)
    } else if (l1 === null && l2 !== null && l1.next === null && l2.next !== null) {
        n.next = new ListNode
        traversal(null, l2.next, s, n.next)
    } else if (l1.next === null && l2.next === null && s) {
        n.next = new ListNode
        traversal(null, null, s, n.next)
    }

}

var addTwoNumbers = function(l1, l2) {
    let storage = 0;
    const result = new ListNode
    traversal(l1, l2, storage, result)
    //console.log(result.next)
    return result
};

Answer 1

I found the problem. It was the way I was passing "null" to every recursion. I added a very lousy condition that checks "l1" or "l2" is null (e.g. l1 === null) as you can see in the code in my question. It was causing various problem in my if/else statement that checks whether l1 or l2 nodes' next value exist or not.

I removed that and decided to change the way I passed "nonexistent" in the form of a node that still has two keys (val, next). Now I can remove the lousy condition and the problem was solved! Here is the code that worked - It's a brute force method but I wanted to make it work.

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */

/*
result = {
    val: 1,
    next: null,
}
*/

const traversal = function(l1, l2, s, n) {
    if (l1 !== null && l2 !== null) {  // result value is all values added
        n.val = l1.val + l2.val + s; //n.val = 1
    } else if (l1 !== null && l2 === null && !s) { //result value is l1 + s
        n.val = l1.val + s;
    } else if (l1 === null && l2 !== null && !s) { //result value is l2 + s
        n.val = l2.val + s;
    } else if (l1 === null && l2 === null && s) { //result value is only s
        n.val = s
    }
    s = 0; //reset storage
    if (n.val > 9) { //false
        s = Number(n.val.toString()[0])
        n.val = Number(n.val.toString()[1])
    }
    let none = {val: null, next: null}
    if (l1.val === null && l2.val === null && !s) { //base case
        return;
    }
    if (l1.next && l2.next) { //both have next node
        n.next = new ListNode
        traversal(l1.next, l2.next, s, n.next)
    } else if (l1.next !== null && l2.next === null) { //only l1 has next node
        n.next = new ListNode
        traversal(l1.next, none, s, n.next)
    } else if (l1.next === null && l2.next !== null) { //only l2 has next node
        n.next = new ListNode
        traversal(none, l2.next, s, n.next)
    } else if (s) { //both has no next node but has a carryover
        n.next = new ListNode
        traversal(none, none, s, n.next)
    }
}

var addTwoNumbers = function(l1, l2) {
    let storage = 0;
    const result = new ListNode
    traversal(l1, l2, storage, result)
    return result
};

Answer 2

Ok, I really couldn't tell what your code was doing, and I apologize for that, but I did have a lot of fun solving this on my own, so here is my complete solution with ES6. You can throw this entire code into an index.js and run it with Node.js if you want to see it in action and play around with it, or just plug it into Leetcode to verify.

function ListNode(val) {
  this.val = val;
  this.next = next;
}

const getValue = (stringVal, node) => {
  return node.next === null
    ? Number(node.val + stringVal)
    : Number(getValue(node.val + stringVal, node.next))
}

const listify = number => number.toString()
  .split('')
  .map(Number)
  .reduce((next, digit) => {
    const node = new ListNode(digit)
    node.next = next
    return node
  }, null)

const addTwoNumbers = (l1, l2) => {
  return listify(getValue('', l1) + getValue('', l2))
}

const first = { val: 2, next: { val: 4, next: { val: 3, next: null} } }
const second = { val: 5, next: { val: 6, next: { val: 4, next: null} } }

addTwoNumbers(first, second)