带递归的链表

Question

早上好，我正在学习，我想用递归函数制作一个链表，我在找例子，但我只找到了Java或其他类型的例子。从我所看到的情况来看，我想会是这样的，但我无法让它发挥作用。如果有人能帮助我，我将不胜感激。非常感谢。

---

function ListRecurse () {
this.head = null;
this.size = 0;
}
function Node () {
this.data = data; 
this.next = next;
}
ListRecurse.prototype.add = function (data) {
let NewNode = new Node(this.add(data), null)
if (this.head === null) {
this.head = NewNode;
}
else {
let current = this.head;
while (current.next) {
current = current.next;
}
current = NewNode
}
this.size ++;
}

---

Answer 1

您的实现中存在以下几个问题：

1. 使用递归会导致堆栈溢出：

   let newNode = new Node(this.add(data));
   

   这只会不断地呼唤自己。此语句下面的代码将永远不会执行。递归总是需要一个基本情况，它将停止递归。

2. Node构造函数缺少参数，因此变量data和next不存在。

3. 分配NewNode时，不应将其分配给current，因为这会破坏列表。您应该将其分配给current.next

有了这些问题的解决，它会起作用，但也要考虑到这些备注：

• 不要用初始资本命名变量，因为通常做法是为构造函数(类(保留这样的符号。所以我会使用名称newNode而不是NewNode
• 对于可能不会在调用中使用的参数，请使用默认值。在您的情况下，您可以给next一个默认值null，这样您就不需要在调用Node时指定null
• 对构造函数使用现代class语法。它导致了更干净的代码
• 允许add方法被链接。所以让它返回this

因此递归实现可能如下所示：

class Node {
// Accept arguments (the second one could be optional)
constructor(data, next=null) {
this.data = data; 
this.next = next;
}
lastNode() { // new method that uses recursion
return this.next?.lastNode() || this;
}
}

class ListRecurse {
constructor() {
this.head = null;
this.size = 0;
}
add(data) {
let newNode = new Node(data); // No second argument. It has a default value
if (this.head === null) {
this.head = newNode;
} else {
// The lastNode implementation uses recursion:
this.head.lastNode().next = newNode;
}
this.size ++;
return this; // to allow chaining
}
}
let list = new ListRecurse();
list.add(1).add(2).add(3);
console.log(list);

递归现在发生在这个语句中，可能需要一些解释：

return this.next?.lastNode() || this;

这将检查当前节点是否有下一个节点引用。如果是，则对lastNode进行递归调用。如果不是，那么我们处于"；基本情况"：具有可选链式运算符(?.(的表达式是undefined，然后OR运算符(||(将启动以返回this，因为它是链中的最后一个节点。

更高效

首先，在这里使用递归可能是一个不错的练习，但它并没有带来太多好处。迭代解决方案很好。

然而，遗憾的是，每次添加节点时都需要遍历整个链表。正如@Nina已经回答的那样，您可以通过维护对尾部节点的引用来避免这种低效性。

Answer 2

您可以利用存储最后一个节点的优势，返回this以获得流畅的接口。

function ListRecurse() {
this.head = null;
this.last = null;
this.size = 0;
}
function Node(data, next) {
this.data = data;
this.next = next;
}
ListRecurse.prototype.add = function(data) {
const node = new Node(data, null);
if (this.head === null) this.head = node;
else this.last.next = node;
this.last = node;  
this.size++;
return this;
}
const list = new ListRecurse().add(1).add(2).add(3);
console.log(list);

.as-console-wrapper { max-height: 100% !important; top: 0; }