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
};

For starters, you need to declare your new nodes properly: new ListNode(0). It's important that you use the parentheses to invoke the constructor function, and pass any necessary parameters. I'm trying to get it to work right now, but maybe you can shed more light on what your addTwoNumbers function is expecting as parameters? — Ben Steward
– Ben Steward, Commented Jan 25, 2019 at 5:40
Yeah, maybe you can provide the exact data we're dealing with as a parameter to our function. Otherwise, It's hard to understand why you've written what you have so far. — Ben Steward
– Ben Steward, Commented Jan 25, 2019 at 5:47
Hey Ben, thank you so much for your help. Here's the full prompt from leetcode: leetcode.com/problems/add-two-numbers — 81ackCat
– 81ackCat, Commented Jan 25, 2019 at 5:49
Thanks, that was pretty critical information, now that I see it. — Ben Steward
– Ben Steward, Commented Jan 25, 2019 at 5:50
No problem! I just saw your edit suggestion and the test input that I'm having trouble with is indeed [1, 8] and [0]. Sorry if the way I wrote may have confused you. — 81ackCat
– 81ackCat, Commented Jan 25, 2019 at 6:21

Ben Steward · Accepted Answer · 2019-01-25 06:20:25Z

1

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)

answered Jan 25, 2019 at 6:20

Ben Steward

2,4171 gold badge15 silver badges26 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

81ackCat Over a year ago

Thank you for your attempt Ben! Your code looks great! But I was hoping that someone could point out what my code is doing wrong... I feel like I'm missing something here.

jessi Over a year ago

This approach works very well within javascript's safe integers. When you exceed max safe integer, getValue will return scientific notation. Therefore, you will have to write a new method to handle very large numbers.

81ackCat · Accepted Answer · 2019-01-25 08:01:53Z

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
};

Collectives™ on Stack Overflow

JavaScript Adding two linkedlist values with recursion

2 Answers 2

2 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related