AlgoDaily - Add Linked List Numbers

Add Linked List Numbers (Hard)

Good morning! Here's our prompt for today.

You may see this problem at Apple, Square, Tableau Software, Robinhood, Jfrog, Mailchimp, Airtable, Netskope, Cockroach Labs, Appian, Motorola, and Nasdaq.

We're provided the following two linked lists:

1 -> 2 -> 3 -> 4 and 2 -> 5 -> 8

Each one represents a number in reversed order, so 1 -> 2 -> 3 -> 4 represents 4321 and 2 -> 5 -> 8 represents 852 (note: for an extra challenge, consider if they weren't reversed).

The lists are guaranteed to have at least one node and will not have any leading 0s. Each of the nodes contain a single digit.

Can you write a method to add the two numbers and return it as another linked list?

JAVASCRIPT

1// list1: 1 -> 2 -> 3 ->4
2// list2: 2 -> 5 -> 8
3
4addLLNums(list1, list2);
5// should return 3 -> 7 -> 1 -> 5
6// 4321 + 852 = 5173

Constraints

Length of both linked lists list1, list2 <= 100000
Value stored in each node is between 0 and 9
Make sure that you have to return a linked list and not a number
Expected time complexity : O(n)
Expected space complexity : O(n)

xxxxxxxxxx
​
 
var assert = require('assert');
​
/*
 * @param {LinkedListNode} list1
 * @param {LinkedListNode} list2
 * @return {LinkedListNode}
 */
​
function addLLNums(list1, list2) {
  // add list1 and list2
  return result;
}
​
function LinkedListNode(val) {
  this.val = val;
  this.next = null;
}
​
var list1 = new LinkedListNode(3);
var nodes1 = [4, 5, 6, 7, 8, 9, 9];
createNodes(list1, nodes1);
​
var list2 = new LinkedListNode(1);
var nodes2 = [2, 3, 4, 5, 6, 7, 8];
createNodes(list2, nodes2);
​
var list3 = new LinkedListNode(1);

OUTPUT

Results will appear here.