Why does my linked list code not work in a modular reusable JavaScript function?

Question

Why does my linked list solution fail when I make my code more modular?

I am tackling question 2 on Leetcode "Add 2 numbers" in linked list format.

Here is the question:

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 contains a single digit. Add the two numbers and return the sum as a linked list.

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

I have a working solution with repetitive code. When I abstract out the body of my last two functions into a reusable function, my solution fails. Why is this?

One assumption I am making is that linked list nodes are objects and should therefore be passed by reference. At least in JavaScript.

Here is my solution that succeeds (before making the code more modular)...

var addTwoNumbers = function(l1, l2) {
    let l3 = new ListNode(0, null);
    let head = l3;
    let carry = 0;
    while (l1 != null && l2 != null) {
        l3.next = new ListNode(carry, null);
        l3 = l3.next;
        let sum = l1.val + l2.val + l3.val;
        let ones = sum % 10;
        carry = Math.floor(sum / 10);
        l3.val = ones;
        l1 = l1.next;
        l2 = l2.next;
    }
    while (l1 != null) {
        l3.next = new ListNode(carry, null);
        l3 = l3.next;
        let sum = l1.val + l3.val;
        let ones = sum % 10;
        carry = Math.floor(sum / 10);
        l3.val = ones;
        l1 = l1.next;
    }
    while (l2 != null) {
        l3.next = new ListNode(carry, null);
        l3 = l3.next;
        let sum = l2.val + l3.val;
        let ones = sum % 10;
        carry = Math.floor(sum / 10);
        l3.val = ones;
        l2 = l2.next;
    }
    if (carry == 1) {
        l3.next = new ListNode(carry, null);
    }
    return head.next;
};

Here is my solution that fails...

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
var addTwoNumbers = function(l1, l2) {
    let l3 = new ListNode(0, null);
    let head = l3;
    let carry = 0;
    while (l1 != null && l2 != null) {
        l3.next = new ListNode(carry, null);
        l3 = l3.next;
        let sum = l1.val + l2.val + l3.val;
        let ones = sum % 10;
        carry = Math.floor(sum / 10);
        l3.val = ones;
        l1 = l1.next;
        l2 = l2.next;
    }
    while (l1 != null) {
        carry = addRemainingNodes(l1, l3, carry);
    }
    while (l2 != null) {
        carry = addRemainingNodes(l2, l3, carry);
    }
    if (carry == 1) {
        l3.next = new ListNode(carry, null);
    }
    return head.next;
};

function addRemainingNodes(la, lb, carry) {
    lb.next = new ListNode(carry, null);
    lb = lb.next;
    let sum = la.val + lb.val;
    let ones = sum % 10;
    carry = Math.floor(sum / 10);
    lb.val = ones;
    la = la.next;
    return carry;
}

trincot · Accepted Answer · 2021-12-08 18:32:13Z

One assumption I am making is that linked list nodes are objects and should therefore be passed by reference.

It is true that they are objects. Variables can have references to those objects. This is not something specific that happens when an argument is passed to a function. So for instance, l3 is a reference. It is this reference that is passed by value to the function, and the local variable lb receives this as its own value (the object reference is copied). When that function assigns to lb, then this only affects that local variable... not to the variable that was used to pass this value to the function.

As a rule of thumb: when a JavaScript function assigns a value to one of its parameter variables, this only has an effect to that local variable¹.

However, when a function mutates a property of a parameter variable, then this will affect the object that was passed as argument.

So concluding, there is no pass-by-reference as can be done in C++. JavaScript uses the pass-by-value mechanics, taking into account that the value of an object really is a reference.

Avoiding code reuse

In your case, the treatment of l3 should be like you treat carry. Just like the function returns carry which got re-assigned, so also it should return l3. This you could do by returning an array with these two values. And then you can use a destructuring assignment at the calling side. This honestly does not look so elegant, but there is a different way to avoid code repetition:

Consider that it will never happen that both the second and the third while loop will make iterations. This is because at most one of l1 and l2 can be non null after the first loop finishes.

So make abstraction of this difference between l1 and l2 and use just one loop to replace these two loops:

    let lrest = l1 || l2; // This will select the non-null list if there is one
    while (lrest != null) {
        l3.next = new ListNode(carry, null);
        l3 = l3.next;
        let sum = lrest.val + l3.val;
        let ones = sum % 10;
        carry = Math.floor(sum / 10);
        l3.val = ones;
        lrest = lrest.next;
    }

^{¹Rare exceptions to this rule exist. There are some alias behaviours like how arguments works in non-strict mode.}

Collectives™ on Stack Overflow

Why does my linked list code not work in a modular reusable JavaScript function?

1 Answer 1

Avoiding code reuse

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Avoiding code reuse

Comments

Your Answer

Sign up or log in

Post as a guest

Related