0

In this question: https://leetcode.com/problems/add-two-numbers/description/, I've figured out how to get sum of the digits (i.e. 807), but now I need to convert that number into a linked list (e.g. 7 -> 0 -> 8).

How do I create a linkedlist from a number?

Class function for creating a list node:

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

Rest of my code:

var addTwoNumbers = function(l1, l2) {

    function findVal(linkedList) {
          return linkedList.next == null ? linkedList.val.toString() : linkedList.val.toString() + findVal(linkedList.next);

    }

    var l1num = parseInt(findVal(l1).split('').reverse().join(''));
    var l2num = parseInt(findVal(l2).split('').reverse().join(''));
    var sum = l1num + l2num;

// Create linked list from sum
doctopus
  • 5,349
  • 8
  • 53
  • 105

2 Answers2

3

If you turn your number into an array, you can then use the array.prototype.reduce function.

let number = 807;

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


// Convert the number into a string and split that into an array of digits
let arr = Array.from(number.toString());

// Iterate through the elements, and create the nodes
let head = arr.reduce((nextNode, curr) => {
  let node = new ListNode(curr);
  node.next = nextNode;
  return node;
}, null);


// Print out the values
let node = head;
while(node) {
  console.log(node.val);
  node = node.next
}
user184994
  • 17,791
  • 1
  • 46
  • 52
  • 1
    You really shouldn't need that `slice(1)`. Just pass `null` as the initial value and use `reduceRight`. – Bergi Dec 06 '17 at 19:08
  • @user184994, almost. The LL are supposed to be in the opposite order. Starting with the ones, then the tens, hundreds, ... so just change the `reduceRight` back to a `reduce` and we should be fine ;) – Thomas Dec 06 '17 at 19:15
  • @Thomas Oh, I didn't notice the OP needs the list backwards. – Bergi Dec 06 '17 at 19:23
  • @Bergi This no longer works following your latest edit- `head` is undefined. You'll need to call `new ListNode` as opposed to `ListNode` – user184994 Dec 06 '17 at 19:30
  • @user184994 Ouch, I didn't mean to remove the `new`. Thanks for testing :-) – Bergi Dec 06 '17 at 19:34
  • I like this reduce solution, but is it possible to reduce it without changing the original class function `ListNode` to accept a 2nd argument `next`? – doctopus Dec 07 '17 at 01:33
  • Yes, it is, I've reverted the changes that were made, so it no longer changes the ListNode – user184994 Dec 07 '17 at 06:03
1

Easier with recursion:

f = n => n ? { val: n % 10, next: f(n / 10 | 0) } : null

console.log( f(807) )

f = (a, b, c = 0) => a && b && { val: (c += a.val + b.val) % 10, 
                                next: f(a.next, b.next, c > 9) } || null

console.log( f( { val: 2, next: { val: 4, next: { val: 3 } } }, 
                { val: 5, next: { val: 6, next: { val: 4 } } } ) )
Slai
  • 22,144
  • 5
  • 45
  • 53
  • what do all the letters represent? – doctopus Dec 07 '17 at 01:23
  • `f = n => n` is short for `function f(n) { return n }`, and I used `a` and `b` instead of the `l1` and `l2` parameters. `c` is just a temporary variable used to get the carry over `+1` if the sum of the 2 digits is more than 9. You can see the translated version on https://www.typescriptlang.org/play/index.html#src=var%20f%20%3D%20n%20%3D%3E%20n%20%3F%20%7B%20val%3A%20n%20%25%2010%2C%20next%3A%20f(n%20%2F%2010%20%7C%200)%20%7D%20%3A%20null – Slai Dec 07 '17 at 01:31
  • how does `n / 10 | 0` work? I just console'd `807 / 10 | 0` and it gave me `80` but no idea how that worked – doctopus Dec 07 '17 at 02:05
  • @cryptofish123 it's one of the shortcuts for converting a floating point number to integer http://blog.blakesimpson.co.uk/read/58-fastest-alternative-to-math-floor-in-javascript. Sorry about making the code so cryptic .. I was going for "Leet" code :D – Slai Dec 07 '17 at 02:13
  • Can you explain how `c > 9` works? On 3rd iteration `c = 10`. I assume you want to carry over only `1` to next iteration? How does it do so ? – doctopus Dec 07 '17 at 03:05
  • true evaluates to 1 and false to 0 when converted to a number https://stackoverflow.com/questions/7820683/convert-boolean-result-into-number-integer so it's shorter than `c / 10 | 0` – Slai Dec 07 '17 at 03:15
  • Didn't know that. Thanks for teaching me some new stuff. Top class answer! – doctopus Dec 07 '17 at 03:27
  • Just realised something withyour first recursion function, if the `n=0` then it only returns `null` – doctopus Dec 07 '17 at 03:56
  • yup, I .. "simplified" it a bit :]. It can be changed to `f = n => n > 9 ? { val: n % 10, next: f(n / 10 | 0) } : { val: n, next: null }` – Slai Dec 07 '17 at 04:05
  • I just noticed another thing too. When n becomes more than 10 digits long it breaks. Why's that? – doctopus Dec 07 '17 at 04:25
  • because the maximum integer is 2^31-1 = 2,147,483,647. You can use `Math.floor` instead of `| 0` for up to almost 16 digits https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Number/MAX_SAFE_INTEGER, or strings for more – Slai Dec 07 '17 at 04:32