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

我将完全忽略您的示例代码，因为我也不理解它。这不是考虑这个问题 IMO 的最简单方法。让我们一起从概念上考虑一下:

1. 如果有人传入一个空列表会怎样？你应该返回一个空列表
2. 如果有人返回一个只有一个元素的列表会怎样？您应该返回传入的内容
3. 如果有人返回两个或更多的列表会怎样？您将列表的 last 元素放在前面，然后调用 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

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