双向链表的排序方法

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对数组进行排序，最后从排序的数组中重建列表。