在链表上迭代时抛出NullPointerException

Question

代码背后的概念是删除列表中比它前面的元素大的元素。在这种情况下，我的节点有一个int数据，并通过它进行比较。(这些类都在extends Comparable<>

问题是当我得到一个nullpointexception时，这段代码运行链表:

 [2,5,4,3,7,6,4,2,3,4,5] 

期望得到的列表是

[2,2]

因为(5> 2)移除5，那么(4> 2)移除4，那么(3> 2)移除3…以此类推，直到它以nullpointerexception结束。

另一个例子是列表

[3,1,-2,3,6,-1,3,2,1]

列表最终应该是

[3,1,-2]

这里的调试代码是用来显示哪些元素被删除了。

getter方法是基本的，工作得很好。

public void deleteIncrementing() {
    T largest = null;
    while(head.getNext() != null || head != null) {
        Node<T> temp = head.getNext();
        while(temp.getValue().compareTo(head.getValue()) > 0){
            largest = temp.getValue();
            remove(largest);
            System.out.println(largest); // debug
            if(temp.getNext() == null){
                break;
            }
            temp = head.getNext();
        }
        head = temp;
    }
}

源自建议的伪代码:

    Node<T> current = head;
    Node<T> previous = null;
    while(current != null) {
        if (previous != null){
            if (current.getValue().compareTo(previous.getValue()) > 0){
                //System.out.println(current.getValue().toString());
                remove(current.getValue());
            }
            if (current.getValue().compareTo(previous.getValue()) < 0){
                //System.out.println(previous.getPrevious().getValue().toString());
                //System.out.println(current.getValue().toString());
                remove(previous.getValue());
            }
        }
        previous = current;
        current  = current.getNext(); 
    }

这仍然是不正确的，因为它没有考虑到第一个到最后一个元素，并保持最后一个附加…任何原因吗?

Answer 1

对于初学者来说，这个条件:

while (head.getNext() != null || head != null)

应:

while (head != null && head.getNext() != null)

总是先检查空!

Answer 2

我不知道这是否是你异常的原因，但是你必须在while循环中切换测试:

while (head != null && head.getNext() != null)

当你第一次测试head.getNext() != null和head为null时，将抛出NullPointerException

更多信息请看这里

Answer 3

你对这个问题想太多了。

考虑需要完成什么:编写一个函数，删除值大于前一个元素的LinkedList元素。

看完这句话后，你应该知道在LinkedList的每个点上需要考虑什么(例如当前元素和前一个元素)。因此，确实不需要嵌套的while循环。

伪代码:

current  = head 
previous = null
while current is not null
   is previous non-null and current > previous?
      if yes: delete current
      if  no: do nothing
   previous = current
   current  = current.next 

看看你是否可以使用这个伪代码来简化你自己的代码

Answer 4

除了其他人提到的head检查不正确之外，我认为这有一些潜在的问题:

    while(temp.getValue().compareTo(head.getValue()) > 0){
        largest = temp.getValue();
        remove(largest);
        System.out.println(largest); // debug
        if(temp.getNext() == null){
            break;
        }
        temp = head.getNext();
    }
    head = temp;

temp表示即将被移除的节点。这个节点发生了什么?我不知道，因为我不知道这是什么列表类型或者remove做什么。但是，除非list类的文档明确说明remove不会影响节点的"next"指针，否则我不会指望它。一般来说，这类数据应该在remove调用之前保存。(在其他语言中，您可能有一个"remove"，也显式地释放存储，肯定有必要先保存链接。)

更严重的问题是，即使"next"指针保持不变，在列表末尾会发生什么?temp指向随后被移除的节点。它的"下一个"指针是null，所以你中断。但是您设置了head = temp，这意味着head现在指向一个不再在列表中的节点。我认为只有当你因为compareTo而到达那个点时，你才需要head = temp——而不是如果你到达那里，因为你到达了列表的末尾。