Sortiermethode für doppelt verknüpfte Liste
-
13-12-2019 - |
Frage
Ich versuche herauszufinden, wie ich meine doppelt verknüpfte Liste sortieren kann.Ich erhalte hier eine Nullzeiger-Ausnahme:
while (temp.getNext()!=null){
Gibt es einen besseren Ansatz oder einen Rat, um dies richtig in Gang zu bringen?
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();
}
}
}
Lösung
Verwenden Sie den Merge Sort Algorithmus, ist oft das beste Wahl zum Sortieren einer (einzelnen oder doppelt verbundenen verknüpften Liste.Es gibt bereits einen post diskutieren die relevanten Umsetzungsfragen.
Andere Tipps
Ich denke, Sie sollten Folgendes überprüfen:
while(temp != null)
weil Sie bereits zuweisen
temp = temp.getNext()
am Ende von while
Schleife.
Der einfache Ansatz besteht darin, den Listeninhalt in ein Array einzufügen, use Arrays.sort
um das Array zu sortieren und schließlich die Liste aus dem sortierten Array neu zu erstellen.
Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow