Вставить связанный список рекурсивно в убывающем порядке

Question

Я изучаю Java и пытаюсь реализовать метод insertList Java LinkedList. Я хочу, чтобы он работал рекурсивно и в порядке убывания. Я следовал учебнику книги, но я застрял в этой точке. Теперь у меня есть следующие коды, которые работают неправильно. Может ли кто-нибудь дать мне несколько советов по этому поводу?

Скажите, мы хотим вставить 1, 3, 9, 0, 5 в 'LinkedList'. После запуска кода он должен быть 9, 5, 3, 1, 0 в «LinkedList».

public class ListElement { 
    int value 
    ListElement next; 
} 

public static ListElement InsertList(ListElement head, ListElement elem) { 

    if(head == null){ 
     elem.next = head; 
     return elem; 
    } 
    else{ 
     if(elem.value > head.value){ 
     elem.next = InsertList(elem, head.next); 
    }else{ 
     elem.next = InsertList(head.next, elem); 
    } 
     return head; 
    } 
} 

Answer 1

У вашего кода есть несколько проблем. Тест

 if(elem.next > head){ 

не следует обобщать, потому что оператор > не определен для объектов. Также кажется, что у вас нет базового аргумента для вашей рекурсии —, которую вы рекурсируете во всех случаях, что вызовет переполнение стека. Наконец, следует вставить значение, а не экземпляр ListElement. Попробуйте вместо этого (я переименовал метод insertList в соответствии с Java конвенциями кодирования):

public static ListElement insertList(ListElement head, int value) { 
    ListElement elt; 
    if (head == null || head.value <= value) { 
     elt = new ListElement(); 
     elt.value = value; 
     elt.next = head; 
     return elt; 
    } else { 
     head.next = insertList(head.next, value); 
     return head; 
    } 
} 

Преимуществом вставки значения вместо ListElement является то, что вы можете скрыть реализацию списка из клиентского кода. Кроме того, поскольку ListElement может быть целым списком, вставка ListElement может иметь неожиданное поведение.

Answer 2

Прежде всего, это не имеет особого значения, но в java-соглашениях наложены методы, начинающиеся с буквы нижнего регистра.

Во-вторых, возможно, вместо вставки вы хотите вызвать insertList (ваша собственная функция), что делает функцию рекурсивной и разумной.

В-третий, необходимо сравнить значение:

if (head == null || elem.value > head.value){ 
    elem.next = head; 
    return elem; 
} 
else { 
    head.next = insertList(head.next, elem); 
    return head; 
} 

Это означает: если головка является нулевой или меньше эля, вставить эль при запуске; в противном случае вставьте его в продолжение списка.