如何通过递归在链表中添加元素?

Question

我做了一个名为"add"的私有递归方法，它应该递归添加元素，但它不起作用。我知道java没有通过引用，那么如何递归添加元素呢？如果你能告诉我我错在哪里，那就太好了。谢谢

public class linkedIt2 {
private int length = 0;
private Node head;

private class Node {
Node next;
int data;
public Node(int data, Node next) {
this.data = data;
this.next = next;
}
public Node(int data) {
this.data = data;
this.next = null;
}
}

public linkedIt2() {
head = null;
}
private void add(Node cur, int data) {
if (cur != null) {
add(cur.next, data);
} else {
cur = new Node(data, null);
}
}
public linkedIt2 insert(int data) {
add(this.head, data);
length++;
return this;
}
}

Answer 1

问题是，您无法更改引用。cur.next 永远不会更改，因为引用是按值调用的。您需要在递归调用之前更改cur.next。

你需要了解Java中"按值调用"的概念，没有按引用调用。引用作为值传输，因此更改引用参数本身，最初使用的对象不会发生任何变化。 也许： http://javadude.com/articles/passbyvalue.htm 让它更清晰。

一种解决方案：类似于您的解决方案：

最初，您必须确保cur不为空。 然后，您可以在函数中访问cur.next。 如果为 null，则结束递归，如果不是，则更深入。

private void add(Node cur, int data) {
if (cur.next != null) {
add(cur.next, data);      
} else {
cur.next = new Node(data, null);
}
}
public linkedIt2 insert(int data) {
if (this.head == null) {
this.head = new Node(data, null);
} else {
add(this.head, data);
}
length++;
return this;
}

或者让 Node 执行递归并操纵自己。正如另一个解决方案所述。那就更好了。

Answer 2

你的错误在行中

cur = new Node(data, null);

当你调用它时，它会更新局部变量cur以指向一个新节点，这实际上不会导致你调用方法的变量更新。举一个更简单的例子

public static void setToFive(int num) {
num = 5;
System.out.println(num); //Always prints 5
}
public static void test() {
int test = 3;
setToFive(test);
System.out.println(test); //Still prints 3 since only num was updated, not test
}

因此，要回到原始问题并递归添加元素，您可以执行以下操作：

private class Node {
//...
public void add(int data) {
if (next == null) {
next = new Node(data, null);
} else {
next.add(data);
}
}

然后只需调用head.add(data(并增加长度计数器。

此版本效果更好，因为当它创建新节点时，它会将类的实例变量设置为指向它，而不是方法中包含的变量。