Is my answer considered cheating? Also, could I use the for loop statement? ( "A List" Exe-CodePudding

As I am doing this part of the exercise,

and nth, which takes a list and a number and returns the element at the given position in the list (with zero referring to the first element) or undefined when there is no such element.

I thought of answering it like this.:

function nth(list, num) {
  return listToArray(list)[num];
}

listToArray (reference):

function listToArray(list) {
  let array = [];
  for (let node = list; node; node = node.rest) {
    array.push(node.value);
  }
  return array;
}

Is this considered cheating? Does it affect optimization, makes the program/function run "slower"? Because it's suppose to be recursive or a while loop according to the solution and as seen on the internet.

In addition, I think there's another way of solving this but I can't wrap my head how to do it, it's implied from the hint of the exercise that the for (let node = list; node; node = node.rest) can be used to access the list for both of the aforementioned functions, but I can't think of a way to use it with the nth function. This is what I am really curious about...

Hint:

To run over a list (in listToArray and nth), a for loop specification like this can be used: for (let node = list; node; node = node.rest)

CodePudding user response：

I think better solution would be add i as counter, increment i on each iteration, and return node when i is equal to num. Time complexity is O(n) (the same as in your solution) but space is O(1) (you don't create new array), for me this is better solution. For small list performance would be the same but for big list with small num this approach would be quicker

function nth(list, num) {
  for (let node = list, i = 0; node; node = node.rest, i  ) {
    if (i === num) {
      return node;
    }
  }
}

function ListNode(val, rest) {
  this.val = val;
  this.rest = rest;
}


const node1 = new ListNode(1);
const node2 = new ListNode(2);
const node3 = new ListNode(3);
node1.rest = node2;
node2.rest = node3;

console.log(nth(node1, 0))

CodePudding user response：

It's not "cheating", but it would be considered bad code due to its inefficiency. Accessing the third element of a linked list should take the same amount of time no matter how long the list is, but your code that converts the list to an array before accessing the third element in the array will have to iterate over the whole list which might be millions of elements.

You would normally write a recursive function

function nth(node, num) {
  if (num < 0 || !list) return undefined;
  else if (num == 0) return node.value;
  else return nth(node.rest, num-1);
}

or an iterative function using the same loop as your toArray implementation, but returning early when reaching the numth value:

function nth(list, num) {
  if (num < 0) return undefined;
  for (let node = list; node; node = node.rest) {
    if (num-- == 0) {
      return node.value;
    }
  }
  return undefined;
}