如何通过递归在列表的最后添加项目？

Question

public class SLList {

    public class IntNode {
        public int item;
        public IntNode next;
        public IntNode(int i, IntNode n){
            item = i;
            next = n;
        }
    }

    public IntNode first;

    public SLList(int x){
        first = new IntNode(x,null);
    }

    public void addFirst(int x){
        first = new IntNode(x, first);
    }

    public int getfirst(){
        return first.item;
    }
    
    public void addLast(int x) {
    
    }
    
    public static void  main(String[] args){
        SLList L =  new SLList(10);
        L.addFirst(5);
        L.addFirst(8);
        L.addLast(9);
        System.out.println(L.getfirst());
    }
}

如何使用递归在列表的最后添加一个项目？我想通过递归添加列表的最后一个，但不能这样做，因为我通过指针指向最后一个元素，所以它返回添加的元素和最后一个元素，而不是整个列表。

Answer 1

设计递归方法时，需要实现两个部分：

• 表示输入的基本情况，很明显预期的输出将是。在您的例子中，最后一个节点是不指向任何其他节点的节点，即其next字段是null。此外，作为预防措施，我们需要在访问其next字段之前解决给定节点为null的情况
• 递归案例——是递归调用发生且方法的主要逻辑驻留的一部分。对于这个任务，递归的情况相当简单：如果当前节点不是null，并且它指向非null节点，那么应该返回下一个节点

为了添加新的最后一个节点，我们首先需要找到对现有节点的引用。

这就是产生最后一个节点的递归方法的样子：

    public IntNode getLast(IntNode curNode) {
        if (curNode == null) {
            return null;
        }
        if (curNode.next == null) {
            return curNode;
        }

        return curNode.next;
    }

注意，getLast（）可以返回一个null。这意味着字段first为null，我们可以将作业委托给方法addFirst（）。否则，将创建该节点的新实例并将其分配给last。下一步。

    public void addLast(int x) {
        IntNode last = getLast(first);
        if (last == null) {
            addFirst(x);
        } else {
            last.next = new IntNode(x, null);
        }
    }