Добавление элемента в отсортированный LinkedList

Question

У меня есть LinkedList из ListElement объектов, и я хотел бы создать метод рекурсивного , который добавляет новые узлы, сохраняя при этом отсортированный порядок списка.

Прямо сейчас у меня есть:

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

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

И я называю это несколько раз с кодом:

ListElement head = null; 
ListElement elem; 

// this block of code is repeated multiple times with values of 3, 8, 20, and 15 
elem - new ListElement(); 
elem.value = 6; 
head = InsertList(head, elem); 

Выход следующим образом:

6 
6 3 
8 6 3 
20 8 6 3 
15 8 6 3 

Этот выход правильный для первых трех строк, но после этого все становится странным. Может ли кто-нибудь улучшить мой алгоритм? Я чувствую, что метод InsertList может быть сокращен намного больше. Благодаря!

Answer 1

Спасибо за помощь и ответы!
Я нашел еще одно сообщение, похожее на мое, и один из ответов на него, похоже, работал на меня.
Вот ссылка для тех, кто хочет видеть: https://stackoverflow.com/a/15936744/1470257

Answer 2

Оператор head = head.next в вашем четвертом условном блоке разрушает элемент head. Я считаю, что это должно быть вместо этого

else if(head.value >= newelem.value) { 
    head.next = InsertList(head.next, newelem); 
} 

Answer 3

При попытке вставить 15, вы входите в 4-е условие:

// 20 > 15 
else if (head.value >= newelem.value) 

, который в свою очередь вызывает InsertList, но проходит 8 в качестве головного узла и, таким образом, попадает в 3-й Состояние:

// 8 < 15 
else if (head.value < newelem.value) 

Вот, вы говорите

newelem.next = head; 

, который устанавливает 15 -> следующая = 8

, а затем вы говорите,

head = newelem; 

который устанавливает глава = 15.

Вы видите проблему? Используйте @ Zim-Zam O'Pootertoot, чтобы исправить ошибку.