java递归地反转链表，有人能带我遍历它吗？

Question

public void reverse(Node curr) {
      if (isEmpty()) {
          return;
      }

      if (curr.next == null) {
          head = curr;
          return;
      }

      reverse(curr.next);
      curr.next.next = curr;
      curr.next = null;

  }

我在学递归。。我的弱点，我只是不明白这是怎么回事。。。我看到它从第二个节点开始。。然后使下一个，下一个，它的链接为空。。。我就是不明白。很抱歉问你这个新问题。我想补充我所了解的。。但不幸的是，事情就是这样

Answer 1

我将完全忽略您的示例代码，因为我也不理解它。在我看来，这不是思考这个问题的最简单方式。让我们一起从概念上思考这个问题：

1. 如果有人通过了一个空名单，会发生什么？你应该返回一个空列表
2. 如果有人返回一个元素的列表，会发生什么？你应该归还传来的东西
3. 如果有人返回两个或更多的列表，会发生什么？将列表中最后一个元素放在前面，然后调用last + reverse(listWithLastRemoved)

---

让我们试着列出两个。它里面有[a, b]。你把它传进来，然后执行第#3步。因此，它确实：

b + reverse([a])

忽略左手边一秒钟reverse([a])将返回[a]，因为它与第#2步匹配。这可以评估为

b + [a]

这可以评估为

[b, a]

请注意，这是伪代码。我用+来暗示在列表的前面添加一个元素

---

让我们再试一次，但这次有3个元素，[a b c]：

[a b c] #apply step #3
c + reverse([a b])  #apply step #3
c + b + reverse([a]) #apply step #2
c + b + [a] #add b to [a]
c + [b a] #add c to [b a]
[c b a]

---

正如您所指出的，要获得最后一个元素，您必须“迭代”列表以找出最后一个元素。这听起来像是必须使用for循环（这不是递归的），但获取最后一个循环也可以递归完成。事实上，它的算法比reverse更简单，从一开始就是一个更好的练习。我将解释getLast的步骤：

1. 如果有人通过了一个空名单，会发生什么？你应该返回null
2. 如果有人返回一个元素的列表，会发生什么？您应该返回第一个元素
3. 如果有人返回两个或更多的列表，会发生什么？删除列表的第一个元素，然后将其余元素传递到getLast

让我们用[a b c]试试：

[a b c] #apply step #3
getLast([b c]) #apply step #3
getLast([c]) #apply step #2
c

请注意，最后一步返回的是一个元素，而不是列表

Answer 2

思考这个问题的一个方法是举一个小例子。首先，两种边缘情况：

1. 如果列表为空，则它已被反转（非常小）
2. 如果curr是一个单独的节点，那么它就是它自己的反转（同样地，很平常）；因此，将当前列表头设置为curr

假设这两个都不成立，那么棘手的事情就是找出最后一块代码是如何工作的。大概整个过程都是通过调用reverse(head)启动的。让我们看看两元素列表会发生什么：

head = curr(0)
  |
  V
+---+  +---+
| 0 |->| 1 |->null
+---+  +---+

由于每个递归调用都会创建一个新的curr，因此我用一个索引注释了curr，以显示递归的应用级别。现在有一个呼叫reverse(curr.next)。在该调用过程中，方法开头的图片如下所示：

head   curr(1)
  |      |
  V      V
+---+  +---+
| 0 |->| 1 |->null
+---+  +---+

这满足了第二种边缘情况，因此该方法将图片更改为：

       head = curr(1)
         |
         V
+---+  +---+
| 0 |->| 1 |->null
+---+  +---+

（请注意，尽管curr是一个单元素列表，但该元素不是head。这就是为什么整个过程都有效的关键！）现在该方法返回，我们回到第一个调用。现在的图片如下所示：

curr(0) head
  |      |
  V      V
+---+  +---+
| 0 |->| 1 |->null
+---+  +---+

第二行代码（在第三个块中）是curr.next.next = curr;。这将图片更改为：

curr(0) head
  |      |
  V      V
+---+  +---+
| 0 |->| 1 |--\
+---+  +---+  |
  ^           |
  |           |
  \-----------/

最后，它设置curr.next = null;：

curr(0)       head
  |             |
  V             V
+---+         +---+
| 0 |->null   | 1 |--\
+---+         +---+  |
  ^                  |
  |                  |
  \------------------/

稍微盯着它看一眼，就会让你相信，事实上，清单是相反的

同样的技术也可以用来观察这如何逆转更长的列表。最简单的方法是调用reverse(curr.next)将反转列表的尾部，接下来的两行将把curr固定到列表的末尾