快速排序与动态链表

Question

我正在尝试为动态链表类制作快速排序方法。但我一直得到一个NullPointerException，不能找出原因。

 private void addToEnd(IntList y){
if(y.head != null ){
        IntNode tmp = this.head;
    while(tmp.getNext() != null){     //line 68
    tmp = tmp.getNext();
}
tmp.setNext(y.head);
}
  }

 public IntList Quicksort(){
if(this.length() > 1){
    IntList bList = new IntList();
    IntList sList = new IntList();
    IntList pivot = new IntList();
    pivot.addNode(head);
    int pivotInt = this.head.getValue();
    IntNode test = this.head.getNext();
    while(test != null){
        if(test.getValue() > pivotInt){
            bList.addNode(test);
        }else{ sList.addNode(test);}
    test = test.getNext();
}
    sList.Quicksort().addToEnd(pivot);
    sList.addToEnd(bList.Quicksort());

}
return this;
}

我在第68行得到NullPointerException，不知道为什么。有人能帮我一下吗?第68行

while(tmp.getNext() != null){     //line 68

Answer 1

我在第68行得到NullPointerException，不知道为什么。

"为什么"是tmp为空:

IntNode tmp = this.head;
while(tmp.getNext() != null){     //line 68

换句话说，this是IntList(我猜)，head字段中有null。

但这是否是一个"有效"的状态，以及(如果不是)它是如何进入那个状态的，这是任何人的猜测。如果这是一个有效的状态，那么修复是重写addToEnd来处理正确添加到空列表的情况;即this.head为空。(事情并不像下面的评论所说的那么简单……但这显然是一个学习练习，所以你可以自己解决。

---

(就我所知，对链表进行排序从来都不是一件容易或有效的事情。简单的方法是将列表元素复制到数组中，对数组进行排序，然后重新填充列表。