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

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

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

基本情况 表示明确预期输出的输入。在你的例子中，last node 是一个不指向任何其他节点的节点，即它的 next 字段是 null。同样作为预防措施，我们需要在访问其 next 字段之前解决 给定节点 为 null 的情况。
递归案例 - 部分递归调用发生并且方法的主要逻辑所在。对于这个任务，递归情况相当简单：如果当前节点不是null并且它指向non-null节点，那么下一个节点应该returned.

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

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

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

        return curNode.next;
    }

请注意，getLast() 可以 return 一个 null。这意味着字段 first 是 null，我们可以将作业委托给方法 addFirst()。否则，将创建节点的新实例并将其分配给 last.next.

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

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

How to add a item at the last in the list by recursion?

java

recursion

list