递归链表逆向器

Question

为 java 项目创建了一个链表 class 并且需要一种方法来反转链表，所以我和我的朋友最终想出了以下递归方法及其辅助方法：

（说明一下，first是链表第一个节点的实例变量）

public void reverse()
{
    first = reverse(first);
}

public Node reverse(Node in) 
{
    if (in == null || in.next == null) 
    {
         return in;
    }

         Node next = in.next;
         in.next = null;
         Node rest = reverse(next);
         next.next = in;
         return rest;
}

当节点包含整数时，我们在列表的开头输入1、2、3（添加为第一个节点时变为3、2、1），然后尝试将3、2、 1 变为 1、2、3 函数按计划工作。

我的问题是我真的无法理解这里发生的事情。

例如，当我跟踪函数（对于 3、2、1）时，显示：

next = in.next（即 2, 1）再次向下传递，直到它只是 (1)，然后向上传递回 rest.但是在递归发生之后，rest 实际上什么也没有发生。它发生在 next.next 身上，我无法弄清楚 next.next 如何以任何方式影响 rest。

我似乎无法找到 rest 在冒泡备份期间从 (1) 到 (1,2) 再到 (1,2,3) 的点。

如果有人能帮助更深入地解释这个函数是如何修改的rest，那就太好了。我已经跟踪这个函数将近 20 次左右，现在试图理解并且正在发生一些我似乎看不到的事情。

我什至把它带给了我的老师，他给了我一些相当于 "If it works, then it works, it's recursion, don't try to understand it." 的废话回复——那是什么建议？？

谢谢

Answer 1

尝试绘制一个包含 2 个节点的列表。这是最简单的例子。

first --> [A] -> [B] -> null

我们调用 reverse(first)，由于 A 不为空，我们得到以下赋值：

in = A
next = B

我们在这一步打破A和B之间的link：

in.next = null;

所以，我们有：

first --> [A]  [B] -> null

现在我们想要剩下的，它被分配给这个函数的递归调用，用 B 代替。我们现在对 B 重复这些步骤，但由于 B.next 为空，我们只剩下 B.

所以，我们得到 B 作为 rest 的结果。我们现在将 next.next 分配给 in，这意味着 B.next 现在是 A。

[B] -> [A] -> null
        ^
      first

我们 return rest 返回给调用它的人，在这种情况下，导致分配给 first.

first --> [B] -> [A] -> null

...现在，列表颠倒了。

这是它的大致分类；看看它的三个节点，你会看到更多的行为。请记住：每个递归调用都会为 in 和 next 创建新变量，并且在我们从该特定方法 return 之前存在的变量将被搁置。

递归链表逆向器

Recursive Linked List Reverser

java

recursion

linked-list