The rubric "help a disabled person". We need a method to insert a new node in the middle of a single-linked list. Stuck at this stage (UPD: self-contained part of the code):

// превращает массив в список function arrayToList() { var number; var list = {number: number, next: list}; for (var i = arrayToList.arguments.length; i > -1; i--) { if (i < arrayToList.arguments.length - 1) list = {number: arrayToList.arguments[i], next: list}; else list = {number: arrayToList.arguments[i], next: null}; } return list; } var list = arrayToList(1,2,3,4,5,7,8,9,10,11,12); // должна вставлять 6 между 5 и 7, но не вставляет function insert(node, list) { if (list.number < node && list.next.number > node) // вставка в середину { var newnode = {number: node, next: list.next}; list.next = newnode; return list; } else if (list.number == node) // узел уже есть return "node " + node + " already exists in the list!"; else if (list.next != null) return insert(node, list.next); // собственно, источник проблемы else // вставка в конец { var newnode = {number: node, next: null}; list.next = newnode; return list; } } console.log(insert(6, list));

Everything works, but not so much: instead of the entire list, that part of it returns from the node that comes before the one that I am going to insert. Those. instead of node1 - node2 - ... - node (n-1) - node (n) - ... only node is returned (n-1) - node (n) - ... (where node (n) is the inserted node ). The point is a recursive call that every time starts a function with a short list. I understood the problem, but I did not find a solution ((Is the recursion justified at all? Maybe it can be a cycle somehow? Or somehow memorize the entire list from beginning to end? Need help.

  • What is the list? How is this function called? - Grundy
  • @Grundy is not a function, it is the list itself into which you need to insert a new node. it (list) is generated by another method from an array. those. at the entrance to this whole circus - an array. a list from it, and you need to add to the list (and delete, but this is the next difficult stage) - Anton Foigt
  • @Grundy Yes, the list is a list, the argument of this function, and it is called somehow Link.insert () - Anton Foigt
  • function insert(node, list) is a function. How is she called? what is passed on to her. call example? - Grundy
  • add a minimal reproducible example so that you can see how it works now - Grundy

1 answer 1

Since only the insert result is important at the first level, it is not necessary to return the results of internal calls to the outside, it is enough to always return the passed list

 // превращает массив в список function arrayToList(...numbers) { return numbers.reduceRight(function(list, number) { return { number: number, next: list }; }, null); } var list = arrayToList(1, 2, 3, 4, 5, 7, 8, 9, 10, 11, 12); // должна вставлять 6 между 5 и 7, но не вставляет function insert(node, list) { if (list.number == node) // узел уже есть return "node " + node + " already exists in the list!"; if (list.number < node && list.next.number > node || list.next == null) // вставка в середину { var newnode = { number: node, next: list.next }; list.next = newnode; } else { insert(node, list.next); // собственно, источник проблемы } return list; } console.log(insert(6, list));

With the cycle it is even easier to run through the list until the conditions are met, add a new item to the right place, and then return the submitted sheet.

 // превращает массив в список function arrayToList(...numbers) { return numbers.reduceRight(function(list, number) { return { number: number, next: list }; }, null); } var list = arrayToList(1, 2, 3, 4, 5, 7, 8, 9, 10, 11, 12); // должна вставлять 6 между 5 и 7, но не вставляет function insert(node, list) { if (list.number == node) // узел уже есть return "node " + node + " already exists in the list!"; var cur = list; while (!(cur.number < node && cur.next.number > node || cur.next == null)) cur = cur.next; cur.next = { number: node, next: cur.next } return list; } console.log(insert(6, list));

  • thanks, kind man! - Anton Foigt