雙向鏈表的排序方法

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) 

，因爲你已經在while循環結束分配

temp = temp.getNext() 

。

Answer 3

簡單的方法是將列表內容放入數組中，使用Arrays.sort對數組進行排序，最後從排序的數組中重建列表。