java - 递归插入排序列表

Question

我需要编写一个方法，将项目递归地插入到单链排序列表中。列表的节点类如下所示：

protected class Node<T> {

    protected Node(T data) {
        this.data = data;
    }

    protected T data;
    protected Node<T> next;
}

protected Node<E> head;

}

方法签名是：void insert(E data)。我可以迭代地做到这一点，但我似乎无法理解如何递归地做到这一点。任何人都可以提供任何见解吗？

Answer 1

假设您应该在列表末尾插入，只需在this.nextuntil this.nextis上重复null。

public void insert(E data) {
    if (this.next == null) {
        // we're at the end, so actually do the insert
        // if you can do it iteratively, you should already know what to do here
    } else {
        this.next.insert(data);
    }
}

Answer 2

创建一个函数，该函数接受一个起始节点和要插入的数据。

如果该节点是放置数据的正确位置，只需插入它。

如果不是，则递归调用该函数以尝试下一个节点。