java - 如何从linkedList中递归删除一个项目？

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 。应该只有一个List，以及0-多个节点。

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

如果您正在查看实现，这就是他们使用节点的原因，而且它也更符合逻辑(列表不包含“列表元素”)等等...

其他一些说明:如果您尝试获取不存在的元素，您的 indexOf 函数将返回错误(1 + null => 错误)。

所以无论如何。您所要做的就是创建一个节点。 (顺便说一句，如果你真的想要一个真正的 LinkedList，你可以使用泛型而不是 int/Integer)。

下面我发布了我的解决方案如何做到这一点(可能更好，但这就是我要做的)。我还编写了一个 toString 方法来查看列表的外观(据我所知，它可以工作)。如果您想在没有 Node 的情况下仍然使用代码，它应该让您了解如何通过删除来解决问题。您还可以将一些逻辑放入 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());
        }
    }
}