Вставка в отсортированный список рекурсивно

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.next до тех пор this.next является 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

Создайте функцию, которая принимает начальный узел и данные для вставки.

Если этот узел является правильным местом для размещения данных, просто вставьте его.

Если нет, вызовите функцию рекурсивно, чтобы попробовать следующий узел.