问Java中的递归链表

EN

正如其他人指出的，您的解决方案比需要的要复杂得多。

首先，请注意，为了遍历列表，您不需要(也可能不想)从列表中删除任何项。

其次，与其检查当前节点的链接是否为null，还可以实际检查当前链接本身是否为null (只要不尝试取消引用，这没有什么问题)。这简化了逻辑。

public String reverse(IntNode head) {
    if (head == null)
        return "";
    else
        return reverse(head.getLink()) + head.getData();
}

或者你甚至可以这样写：

public String reverse(IntNode head) {
    return (head == null)? "" : reverse(head.getLink()) + head.getData();
}

这段代码比需要的要复杂得多。在这种情况下，可以将递归分解为2种情况(或函数可能具有的2条执行路径)：

1. Recursive大小写：此路径调用自身，以便递归可以启动(或continue)
2. Base大小写：此路径结束递归时不调用

)

您的代码有两个基本情况，它只需要1。考虑所有可以调用函数的输入：

1. head is null
2. head是IntNodea. head.getLink()返回null

b. IntNode返回一个head.getLink()

1. `head.getLink().getLink()` returns `null`
2. `head.getLink().getLink()` returns an `IntNode`

​

您将开始注意到一个模式；一旦将其简化，实际上只有两个可能的输入：

1. head is null
2. head是IntNode

如果head是一个IntNode，则该函数可以用head.getLink() (递归大小写)调用自己，并且只能是相同的2个输入，这种情况一直持续到head变成null (大小写)为止。

为了回答您的实际问题，它只返回最后一个元素的值，因为在递归的情况下，您实际上并不是在当前IntNode的值(即head.getData())前面；您只是返回下一个reverse()调用的结果，这意味着它将递归到最后一个元素，然后只返回该元素的值。

当考虑递归时，这是一个很好的策略，从地面建立，直到你遇到有趣的案例。在每个步骤中，尝试重用以前的案例。

Q1。空列表的反面是什么？

A1。一张空名单。[]

Q2。有一个元素的列表的反向是什么？

A2。同样的名单。1

Q3。有两个元素的列表的反向是什么?12

A3。第一个元素，附加到第二个元素。 2 1

Q4。有三个元素的列表的反面是什么?12，2，3

A4。第一个元素，追加到其余元素列表的反向。3 2+1=3 2 1

现在，模式应该变得清晰了:N元素列表的反向是最后一个N1元素的反向，并附加了第一个元素)。

我们的基本情况是什么？从上面可以看出，它有一个包含1或0元素的列表。但是，仔细看看，将我们的模式应用到长度为1的列表中，我们会发现，带有第一个元素的反转是[]，即[] +1。所以，实际上，我们的基本情况只是空的列表。