递归地反转链接列表,有人可以引导我通过吗？

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;

  }

我正在努力学习递归..我最薄弱的一点,我只是不明白它是如何工作的...我看到它从第二个节点开始......然后使下一个,在当前的旁边,它的链接为null ...我只是不明白.抱歉新问题.我会添加更多我理解的东西..但不幸的是,这真的是关于它...

Answer 1

我将完全忽略您的示例代码,因为我也不理解它.这不是思考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

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