Сортировать метод для вдвойне связанного списка
-
13-12-2019 - |
Вопрос
пытается выяснить, как сортировать мой вдвойне связанный список. Я получаю исключение NULL указателя здесь:
while (temp.getNext()!=null){
.
Есть ли лучший подход или любой совет, чтобы получить это правильно?
public void sort() {
//bubble sort!
boolean swapped = (head != null);
while (swapped) {
swapped = false;
EntryNode temp = head;
//can't swap something with nothing
while (temp.getNext()!=null){
if (temp.getLastName().compareTo(temp.getNext().getLastName()) > 0) {
swapped = true;
//special case for two nodes
if (size == 2) {
//reassign head and tail
tail = temp;
head = temp.getNext();
tail.setPrev(head);
head.setNext(tail);
tail.setNext(null);
head.setNext(null);
}
//if swapping is at head
else {
if (temp == head) {
head = temp.getNext();
temp.setNext(head.getNext());
head.getNext().setPrev(temp);
head.setPrev(null);
head.setNext(temp);
temp.setPrev(head);
}
else {
temp.setNext(temp.getNext().getNext());
temp.setPrev(temp.getNext());
temp.getNext().setNext(temp);
temp.getNext().setPrev(temp.getPrev());
}
}
}
//loop through list
temp = temp.getNext();
}
}
}
. Решение
Используйте Сортировка слияния алгоритма, часто является Лучший выбор для сортировки (одно- или вдвойне) связанный список.Уже уже есть post Обсуждение соответствующих вопросов реализации.
.Другие советы
Я думаю, что вы должны проверить:
while(temp != null)
.
Потому что вы уже назначаете
temp = temp.getNext()
.
в конце цикла Gensacodicetacode.
Простой подход - поставить содержимое списка в массив, используйте Arrays.sort
для сортировки массива и, наконец, восстановить список из отсортированного массива.
Не связан с StackOverflow