用递归-Java实现单链表的反向打印

Question

input: [1, 2, 3, 4, 5] and output:[5, 4, 3, 2, 1]

public String printReverse() {
    StringBuilder myString = new StringBuilder("[");
    if (head != null) { // base case
        head = head.next;
        myString.append(head.value);   // line 406
        myString.append(", ");         // line 407
        printReverse();                // line 408
    }
    myString = myString.append("]");
    return myString.toString();
}

Exception in thread "main" java.lang.NullPointerException
    at myprog.SLL$Node.access$100(SLL.java:445)

    at myprog.SLL.printReverse(SLL.java:406)

    at myprog.SLL.printReverse(SLL.java:408)

    at myprog.SLL.printReverse(SLL.java:408)

    at myprog.SLL.printReverse(SLL.java:408)

    at myprog.SLL.printReverse(SLL.java:408)

    at myprog.SLLApp.myMethod(SLLApp.java:198)

    at myprog.SLLApp.<init>(SLLApp.java:37)

    at myprog.SLLApp.main(SLLApp.java:26)

Answer 1

你太把事情复杂化了。让我们看看伪代码：

• 初始节点为head
• 如果next为空打印空白（递归终止条件）
• 否则递归到下一个节点
• 然后打印当前节点

在代码中，这将变为：

public String printReverse() {
    return printReverse(head); 
}

private String printReverse(Node n) {
    return next == null ? "" : (printReverse(next) + n.value);
}