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

  }

我正在尝试学习递归..我的弱点，我只是不明白这是如何工作的...我看到它从第二个节点开始..然后在当前节点旁边进行下一个，它的链接为空...我只是不明白。对不起新问题。我会在我所理解的基础上添加更多内容。但不幸的是，这就是它的真正意义。

4

5 回答 5

6

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

  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

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

于 2013-06-17T23:20:41.333 回答
2

这是一些伪代码来说明解决方案

// method takes a list and returns the list reversed
// it will corrupt the existing list so do not use it
// after calling this method.
// works by finding the last node and building a list from there
public Node reverseList(Node list){
    // have we found the last node yet?
    if (list.isLast()){
        return list;
    } else {
      // reverse the list after the current node
      Node newList = reverseList(list.next());
      // add current node to end of new list
      addToLast(list,node);
      // return new list
      return newList;
    }

}

public void addToLast(Node list, Node newNode){
    // add newNode to the end of list.
}
于 2013-06-17T23:22:40.940 回答
1

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

  1. 如果列表为空，则它已经被反转（很简单）
  2. ifcurr是单个节点，它是它自己的反转（再次，微不足道）；因此将当前列表头设置为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到列表的末尾。

于 2013-06-17T23:34:06.357 回答
1

由于您要求进行演练：

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

如果已到达列表的末尾，则无需执行任何操作。

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

当参数是列表的最后一个节点 ( curr.next == null) 时，我们设置head为该节点，因为原始的最后一个节点是反向列表的第一个节点。

      reverse(curr.next);

否则，我们反转列表的尾部（当前节点之后的所有内容）。结果列表的最后一个节点是curr.next，因为这是我们在这里反转的列表的第一个节点。

      curr.next.next = curr;

我们将当前节点附加到反向列表的末尾。方便的是，我们仍然引用了最后一个节点，即curr.next.

      curr.next = null;

我们将next当前节点的字段设置为null，因为它是反向列表的最后一个节点。

}
于 2013-06-17T23:34:45.923 回答
1

起初这对我来说也有点奇怪，但它实际上很有意义：

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

      if (curr.next == null) //once we get to the last element, assign it to head
      {
          head = curr;
          return;
      }

      //explained below
      reverse(curr.next); 
      curr.next.next = curr;
      curr.next = null;  
  }

让我们通过考虑倒数第二个元素的情况来分析最后三行。

我们调用reverse(curr.next)，并且由于在该调用中curr.next == null，我们head = curr，在这种情况下curr是最后一个元素，然后返回。

现在， atcurr.next.next = curr再次curr是原始列表中倒数第二个元素。

curr.next是原始的最后一个元素，curr.next.next = curr并将原始列表中的倒数第二个元素分配为原始列表中最后一个元素的下一个元素。

curr.next = null然后next在 list 中创建元素（第三个）null。我们重复并因此向后增长列表（最后一个元素将是null）。

如果这仍然没有意义，请尝试抓住三个对象：钢笔、书本、你有什么，并用一个来表示curr，一个来表示curr.next，一个来表示curr.next.next/ null。如果您跟踪调用并使用现实生活中的对象来帮助您跟踪事物，这可能会有所帮助。希望这可以解决问题。祝你好运。

于 2013-06-17T23:43:24.750 回答