如何递归地从链接列表中删除项目?

Question

以递归方法实现LinkedList对我来说有点挑战，我陷入了实现其remove方法的困境，想知道如何在递归中保持对前一项的引用？

MyLinkedList 类

package linkedlist;
public class MyLinkedList {
private Integer value;
private MyLinkedList next;
public MyLinkedList() {
}
public MyLinkedList(Integer value) {
this.value = value;
}
public void add(Integer value) {
if (this.value == null) {
this.value = value;
} else if (this.next == null) {
this.next = new MyLinkedList(value);
} else {
this.next.add(value);
}
}
public MyLinkedList remove(Integer index) {
//
//        if (index < 0) {
//            return this;
//        }
//        if (index == 0) {
//            return this.next;
//        }
//        this.next = remove(index - 1);
return this;
}
public Integer indexOf(Integer value) {
if (this.value.equals(value)) {
return 0;
} else if (this.next == null) {
return null;
} else {
return 1 + this.next.indexOf(value);
}
}
}

MyLinkedListTester 类

package linkedlist;
public class MyLinkedListTester {
public static void main(String[] args) {
MyLinkedList myLinkedList = new MyLinkedList();
myLinkedList.add(1);
myLinkedList.add(2);
myLinkedList.add(3);
myLinkedList.add(4);
System.out.println("Index Of Array: " + myLinkedList.indexOf(3));
MyLinkedList linkedList = myLinkedList.remove(3);
}
}

Answer 1

正如评论中提到的，迭代方法在大多数情况下更容易、更有效。无论如何，我认为你这样做是一个练习，因为在Java中你已经有一个LinkedList。

所以首先你的思维有一种错误(据我所知(。这也是一种糟糕的设计选择。您创建MyLinkedList并将数据直接保存到其中，下一个也是类MyLinkedList，但它不是列表，而是Node。应该只有一个列表，0 - 许多节点。

例如，我不知道如何执行一个删除函数，该函数将返回已删除的Node(在您的情况下MyLinkedList(，并且还可以让您保留列表，以防您删除列表中的第一个元素。

如果您正在寻找实现，这就是他们使用 Nodes 的原因，而且它也更合乎逻辑(列表不包含"列表元素"(等等......

其他一些评论：如果您尝试获取不存在的元素，您的indexOf功能将返回错误(1 + null => 错误(。

所以无论如何。你要做的是创建一个Node.(顺便说一句，如果你真的想要一个真正的 LinkedList，你可以使用 generic 而不是 int/Integer(。

下面我发布了我的解决方案如何做到这一点(可能更好，但这就是我会这样做的方式(。我还编写了一个toString方法来查看列表的外观(据我所知，它的工作原理(。如果你想在没有节点的情况下仍然使用你的代码，它应该给你一个想法，如何解决你的问题删除。你也可以把一些逻辑放到Node类中，但对我来说Node只是一个容器，并不真正包含任何逻辑。

public class MyLinkedList {
private Node head;
public MyLinkedList() {
}
public class Node{
private int value;
private Node next = null;
public Node(int value){
this.value = value;
}
public int getValue(){
return value;
}
public Node getNext(){
return next;
}
public void setNext(Node next){
this.next = next;
}
}
public void add(int value) {
Node next = new Node(value);
if(head == null){
head = next;
} else {
addRecursive(head,next);
}
}
private void addRecursive(Node node, Node next) {
if(node.next == null){
node.setNext(next);
} else {
addRecursive(node.getNext(),next);
}
}
public Node remove(int index){
Node removeNode = head;
if(index == 0){
head = head.getNext();
} else {
removeNode = removeRecursive(head,index-1);
}
return removeNode;
}
private Node removeRecursive(Node node, int index){
Node removeNode = node.getNext();
if(index == 0){
node.setNext(removeNode.getNext());
} else {
removeNode = removeRecursive(node.getNext(),index-1);
}
return removeNode;
}
public int indexOf(int value) {
if (head == null){
return -1;
}  else if (head.getValue() == value){
return 0;
} else {
return indexOfRecursive(head,value,0);
}
}
private int indexOfRecursive(Node node, int value, int index) {
if(node.getNext() == null){
return -1;
} else if(node.getNext().getValue() == value){
return index + 1;
} else {
return indexOfRecursive(node.getNext(),value,index+1);
}
}
@Override
public String toString(){
if(head == null){
return "";
} else {
return toStringRecursive(head,"["+head.getValue());
}
}
private String toStringRecursive(Node node, String output){
if(node.getNext() == null){
return output + "]";
} else {
return toStringRecursive(node.getNext(),output + ", " + node.getNext().getValue());
}
}
}