2
\$\begingroup\$

I solved a problem with JavaScript which has the following requirements:

  1. Two non-empty linked lists representing two non-negative integers.
  2. Digits stored in reverse order
  3. Each node contains a single digit
  4. Add the two numbers and return it as a linked list

Sample I/O:

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807

My code:

 /**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
var addTwoNumbers = function(l1, l2) {
  let l1Str = "";
  let l2Str = "";
  while (l1 !== null) {
    l1Str += l1.val.toString();
    l1 = l1.next;
  }

  while (l2 !== null) {
    l2Str += l2.val.toString();
    l2 = l2.next;
  }

  let sum = (BigInt(l1Str.split("").reverse().join("")) + BigInt(l2Str.split("").reverse().join(""))).toString();

  let resultNodeList = new ListNode(sum[sum.length - 1]);
  let resultHead = resultNodeList;
  for (let i = sum.length - 2;i >= 0;i--) {
    resultNodeList.next = new ListNode(sum[i]);
    resultNodeList = resultNodeList.next;
  }

  return resultHead;

};

Note: I had to use BigInt cause parseInt won't work on big integers as expected.

Although it passed all test cases, what are some ways to improve this code in terms of both time and space complexity?

\$\endgroup\$
1
  • \$\begingroup\$ In my opinion, using BigInt to perform the addition is considered cheating. \$\endgroup\$ Commented Jun 15, 2019 at 7:09

1 Answer 1

Reset to default
2
\$\begingroup\$

Here are a list of improvements:

  1. Use ECMAScript features and syntax
  2. Create own implementation of BigInt
  3. Don't use strings !
  4. Create functions to regroup similar code and reduce code duplication

Detailed Explanation:

Generates a ListNode from a given array (array should already be reversed).

generateListNode = (list) => {
 const [ele] = list;
 //create the sentinel (starting point of the node list)
 const sentinel = new ListNode(ele);
 let current = sentinel;
 for(let i = 1; i < list.length; i++){
   //update the next with the new list node
   //set the current to the new next
   current = current.next = new ListNode(list[i]);
 }
 return sentinel;
}

Convert a ListNode to an Array

const convertToValueList = (list) => {
  const res = [];
  //as long as the value "list" is not null it'll continue the loop
  //push the list.val to the result array
  do { res.push(list.val); } while(list = list.next);
  return res;
}

addTwoNumbers has it's own implementation of BigInt

const addTwoNumbers = function(l1, l2) {

  //Convert the ListNode to arrays
  const l1Values = convertToValueList(l1);
  const l2Values = convertToValueList(l2);

  //find the longest of either list
  const len = Math.max(l1Values.length, l2Values.length);

  //when adding a column, value should not exceed 9, otherwise it'll be set to the remainder
  //i.e.: 10 -> 1, 23 -> 2, 30 -> 3
  let remainder = 0;
  //final result in reverse
  const sum = [];
  for (let i = 0; i < len; i++) {
    //add the sum of each value of the list at the "i" position
    //if the value does not exist (i.e.: undefined) use default 0
    //add the remainder if it exists
    const tempSum = (l1Values[i] || 0) + (l2Values[i] || 0) + remainder;
    //update the remainder (any value under 10 is set to 0 because of Math.floor)
    remainder = Math.max(Math.floor(tempSum/10), 0);
    //add the value (modulo 10 so only numbers 0 - 9 are added)
    sum.push(tempSum % 10);
  }

  console.log(sum);
  //generate the list node and return final result
  return generateListNode(sum);
};

Working Example:

class ListNode {
  constructor(val){
    this.val = val;
    this.next = null;
  }  
}

generateListNode = (list) => {
  const [ele] = list;
  const sentinel = new ListNode(ele);
  let current = sentinel;
  for(let i = 1; i < list.length; i++){
    current = current.next = new ListNode(list[i]);
  }
  return sentinel;
}

const list1 = generateListNode([2, 4, 3]);
const list2 = generateListNode([5, 6, 4]);

const convertToValueList = (list) => {
  const res = [];
  do { res.push(list.val); } while(list = list.next);
  return res;
}

const addTwoNumbers = function(l1, l2) {

  const l1Values = convertToValueList(l1);
  const l2Values = convertToValueList(l2);
  
  const len = Math.max(l1Values.length, l2Values.length);
  
  let remainder = 0;
  const sum = [];
  for(let i = 0; i < len; i++){
     const tempSum = (l1Values[i] || 0) + (l2Values[i] || 0) + remainder;
remainder = Math.floor(tempSum/10);
     sum.push(tempSum % 10);
  }

  console.log(sum);
  return generateListNode(sum);
};

const res = addTwoNumbers(list1, list2);
console.log(res);

Additional:

The best case scenario is if you have the option to add methods to ListNode.

class BodyNode {
  constructor(val){
    this.val = val;
    this.next = null;
  }
}

class ListNode extends BodyNode {
  
  static FromArray(list){
     if(list.length === 0) throw new Error("Array cannot be of length 0");
     const clone = list.slice();
     const instance = new ListNode(clone.shift());
     while(clone.length > 0){
       instance.add(clone.shift());
     }
     return instance;
  }

  constructor(val){
    super(val);
    this.last = this;
  }
  
  add(val){
    this.last = this.last.next = new BodyNode(val);
  }
  
  toArray(){
    const res = [];
    let current = this;
    do { res.push(current.val); } while(current = current.next);
    return res;
  }
  
}

const list1 = ListNode.FromArray([2, 4, 3]);
const list2 = ListNode.FromArray([5, 6, 4]);

const addTwoNumbers = function(l1, l2) {

  const l1Arr = l1.toArray();
  const l2Arr = l2.toArray();
  
  const len = Math.max(l1Arr.length, l2Arr.length);
  
  let remainder = 0;
  const sum = [];
  for(let i = 0; i < len; i++){
     const tempSum = (l1Arr[i] || 0) + (l2Arr[i] || 0) + remainder;
     remainder = Math.floor(tempSum/10);
     sum.push(tempSum % 10);
  }

  console.log(sum);
  return ListNode.FromArray(sum);
};

const res = addTwoNumbers(list1, list2);
console.log(res);

\$\endgroup\$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.