练习单向链表实现，被我的列表反转方法抛出 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();
}
}

问题出在我的反向列表（节点）方法上。当我运行该程序时，出现以下错误：

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);

My printNodeValues 工作正常，并打印

0 1 2 3 4 5 6 7 8 9

我正在尝试使用反向列表打印

9 8 7 6 5 4 3 2 1 0.

Answer 1

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

然后，列表

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

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;
}

Answer 2

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);