java - 递归地将新节点添加到 LinkedList 的末尾？

Question

尝试编写递归方法将新节点添加到 LinkedList 末尾时遇到很多麻烦。我已经盯着这个很久了，但我的终端仍然打印空白......如果有人可以帮助我，我将不胜感激!仍在尝试理解递归的概念。如果我尝试使用 while 循环迭代地解决问题，那么我可以毫无问题地完成它，但我的作业要求我递归地编写它。感谢您的帮助:)

public class LinkedList
{
    //
    //Instance variable
    //
    private Node top;


    //
    //Instance and static methods below
    //

    //Accessor for the top Node
    public Node getTop()
    {
        return top;
    }

    public void add(Object data) {
        Node newNode = new Node(data,null);
        addRec(top,newNode);
}

    private Node addRec(Node start, Node newNode) {
        if (start == null) {
            start = newNode;
            return start;
        }
        start.setLink(addRec(start.getLink(), newNode));
        return start;
    }

    public String toString() {
        String value = "";
        Node current = top;
        while (current != null) {
            value += current.getData();
            current = current.getLink();
        }
        return value;
    }

节点类:

public class Node
{
    //
    //Instance variables
    //
    private Object data;
    private Node link;

    //
    //Constructor
    //
    public Node (Object initData, Node initLink)
    {
        data = initData;
        link = initLink;
    }

    //
    //Accessors
    //
    public Object getData()
    {
        return data;
    }

    public Node getLink()
    {
        return link;
    }

    public void setData(Object data) {
        this.data = data;
    }

    //
    //Mutators
    //
    public void setLink(Node newLink)
    {
        link = newLink;
    }
}

Answer 1

递归地将节点添加到链表中是一个相当简单的概念。让我们看一下算法:

1] 如果给定节点后面没有节点(我们将其称为下一个节点)，我们将添加当前节点。

2] 否则，我们将该节点添加到下一个节点。这将涉及在下一个节点上执行步骤 1。

如果您注意到，步骤 2 对步骤 1 进行了递归调用，因为它引用了同一节点。

为了实现这一点，首先，我们在 LinkedList 中创建一个名为 Node 的子类。这将需要一个 int 来存储数据，以及一个指向下一个 Node 的 Node。

我们在 Node 内部创建了 add() 方法。

为了实现步骤 1，我们检查 next 是否等于 null。如果是，我们将该节点添加为链表上的下一个节点。

if(this.next== null)this.next= toAdd;

为了实现步骤 2，否则我们会在下一个 Node 上调用 add 方法，并将值传递给 add。

if(this.next== null)this.next= toAdd;

现在，我们必须在 LinkedList 类中实现它。

我们声明一个根节点，列表从这里开始。

现在，我们声明一个方法来执行以下操作:

向根添加一个值。

就是这样。

递归会处理剩下的事情。

想一想，如果root后面有一个节点，那么数据就会添加到下一个节点，依此类推。

因此，问题解决后，您就有了 list !

    public class LinkedList
{
    private Node root;

    private class Node{
        int data;
        Node next;
        public Node(int data){

            this.data = data;
            this.next = null;

        }

        public void add(Node toAdd){

            if(this.next== null)this.next= toAdd;
            else this.next.add(toAdd);

        }

    }

    public LinkedList(int root){

        this.root = new Node(root);
    }

    public void add(int toAdd){
        this.root.add(new Node(toAdd));
    }
}