练习单链表实现，被我的列表反转方法抛出NullPointerException难住了

Question

这是我的单链表代码：

public class SinglyLinkedList {

private static Node head;
private static int listSize;

private static class Node {

    int value;
    Node next;

    Node(int i) {
        value = i;
        next = null;
    }
}

public static void main(String[] args) {
    head = null;
    listSize = 0;
    for (int i = 0; i < 10; i++) {
        Node n = new Node(i);
        if (head == null) {
            head = n;
        } else {
            getLastNode(head).next = n;
        }
        listSize++;
    }
    printNodeValues(head);
    Node revHead = reverseList(head);
    printNodeValues(revHead);
}

private static Node reverseList(Node head) {
    Node reverseHead = getLastNode(head);
    Node reference = reverseHead;
    while (listSize>0){
        Node temp = getPreviousNode(reference, head);
        Node last = getLastNode(reverseHead);
        temp.next = null;
        last.next = temp;
        reference = temp;
        listSize--;
    }
    return reverseHead;
}

private static Node getPreviousNode(Node reference, Node head) {
    Node temp = head;
    while (temp != null) {
        if (temp.next == reference) {
            break;
        } else {
            temp = temp.next;
        }
    }
    return temp;
}

private static Node getLastNode(Node n) {
    Node temp = n;
    while (temp != null) {
        if (temp.next == null) {
            break;
        } else {
            temp = temp.next;
        }
    }
    return temp;
}

public static void printNodeValues(Node h) {
    while (h != null) {
        System.out.print(h.value + " ");
        h = h.next;
    }
    System.out.println();
}
}

问题出在我的 reverseList(Node) 方法上。当我运行程序时，出现以下错误：

Exception in thread "main" java.lang.NullPointerException
at SinglyLinkedList.reverseList(SinglyLinkedList.java:44) -> temp = null;
at SinglyLinkedList.main(SinglyLinkedList.java:33) -> Node revHead = reverseList(head);

我的 printNodeValues 工作正常，并打印

0 1 2 3 4 5 6 7 8 9

我正在尝试使用 reverseList 打印

9 8 7 6 5 4 3 2 1 0.

Answer 1

您的 reverseList() 方法在到达原始列表中的第一个节点时需要跳过迭代，因为它的前一个节点不存在。这个第一个节点已经被分配为倒数第二个迭代（原始循环的）中的下一个节点（即反向列表中的最后一个节点）。

private static Node reverseList(Node head) {
    Node reverseHead = getLastNode(head);
    Node reference = reverseHead;

    int counter = listSize; 
    while ( counter > 1) {
        Node temp = getPreviousNode(reference, head);
        Node last = getLastNode(reverseHead);
        temp.next = null;
        last.next = temp;
        reference = temp;
        counter--;
    }
    return reverseHead;
}

其次，您不应该直接修改 listSize 变量，因为反向列表中的元素数量保持不变。在这里，我先将其存储在临时 counter 中，然后再迭代列表。

而且，最后反转的列表应该成为您当前的 head。因为，您已经修改了所有元素之间的链接，所以只有当您的 head 现在指向新的 head.

时才能遍历它

printNodeValues(head);
head = reverseList(head);
printNodeValues(head);

Answer 2

你的代码中有很多非常糟糕的地方。最糟糕的是：为什么一切都是静态的？编写一个只能实例化一次的列表 class 有什么意义？

那么，列表的大小永远不会受到反向操作的影响，您甚至不需要计数器，因为您只需要遍历列表直到找到没有后继的节点。

private static Node reverseList(Node head) {
    Node res = null;    
    while (head != null) {
        Node node = new Node(head.value);
        node.next = res;
        res       = node;
        head      = head.next;
    }    
    return res;
}

练习单链表实现，被我的列表反转方法抛出NullPointerException难住了

Practicing Singly Linked List implementation, stumped by my list reversal method throwing NullPointerException

java

linked-list

nullpointerexception