基于以下观察，这个问题有一个很好的递归解决方案：

There's a great recursive solution to this problem based on the following observations:

1. 空列表的反面是空列表。


2. 单例列表的反向本身。


3. 列表的反向节点N后跟列表L的后面是列表L的反向，后跟节点N.

因此，您可以实现使用伪代码沿这些行的反向函数：

You can therefore implement the reverse function using pseudocode along these lines:

void reverseList(Node node) {
    if (node == null) return;      // Reverse of empty list is itself.
    if (node.next == null) return; // Reverse of singleton list is itself.

    reverseList(node.next); // Reverse the rest of the list
    appendNodeToList(node, node.next); // Append the new value.
}

此算法的简单实现在O（n ² ），因为每次反转都需要一个追加，这需要对列表的其余部分进行O（n）扫描。但是，您实际上可以使用聪明的观察在O（n）中使用它。假设您有一个如下所示的链接列表：

A naive implementation of this algorithm runs in O(n²), since each reversal requires an append, which requires an O(n) scan over the rest of the list. However, you can actually get this working in O(n) using a clever observation. Suppose that you have a linked list that looks like this:

n1 --> n2 --> [rest of the list]

如果从n2开始反转列表，那么你最终会得到这个设置：

If you reverse the list beginning at n2, then you end up with this setup:

n1       [reverse of rest of the list] --> n2
 |                                          ^
 +------------------------------------------+

因此，您可以通过设置将n1附加到列表其余部分的反面n1.next.next = n1 ，更改 n2 ，反向列表的新结尾，指向n1：

So you can append n1 to the reverse of the rest of the list by setting n1.next.next = n1, which changes n2, the new end of the reverse list, to point at n1:

[reverse of the rest of the list] --> n2 --> n1

你是金色的！再次更多伪代码：

And you're golden! Again more pseudocode:

void reverseList(Node node) {
    if (node == null) return;      // Reverse of empty list is itself.
    if (node.next == null) return; // Reverse of singleton list is itself.

    reverseList(node.next); // Reverse the rest of the list
    node.next.next = node; // Append the new value.
}

编辑：正如Ran指出的那样，它使用调用堆栈作为其存储空间因此存在堆栈溢出的风险。如果你想使用显式堆栈，你可以这样做：

As Ran pointed out, this uses the call stack for its storage space and thus risks a stack overflow. If you want to use an explicit stack instead, you can do so like this:

void reverseList(Node node) {
    /* Make a stack of the reverse of the nodes. */
    Stack<Node> s = new Stack<Node>();
    for (Node curr = node; node != null; node = node.next)
        s.push(curr);

    /* Start unwinding it. */
    Node curr = null;
    while (!s.empty()) {
        Node top = s.pop();

        /* If there is no node in the list yet, set it to the current node. */
        if (curr == null)
            curr = top;
        /* Otherwise, have the current node point to this next node. */
        else
            curr.next = top;

        /* Update the current pointer to be this new node. */
        curr = top;
    }
}

我认为这类似地反转了链表元素。

I believe that this similarly inverts the linked list elements.