Метод сортировки для двусвязного списка

Question

Попытка выяснить, как сортировать мой список, связанный дважды. я получаю исключение нулевого указателя здесь:

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(); 
     } 
    } 
} 

Answer 1

Использование алгоритма merge sort, часто является best choice для сортировки (одного или двух) связанных списков. Уже есть post, где обсуждаются соответствующие проблемы реализации.

Answer 2

Я думаю, вы должны проверить:

while(temp != null) 

, потому что вы уже назначая

temp = temp.getNext() 

в конце цикла while.

Answer 3

Простой подход состоит в том, чтобы поместить содержимое списка в массив, используйте Arrays.sort для сортировки массива и, наконец, перестройте список из отсортированного массива.