对这个链表的递归逆向器中的 return variable/value 感到困惑

Question

前几天我问了一个类似的问题，但当涉及到这个递归 linked 列表反转方法如何工作的细节时，我并没有真正得到我想要的答案。

我有以下方法：

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

如果我在递归调用后修改 current 变量，但 return 正在 rest，rest 如何成为下一个 modified/appended link 在列表中？当我跟踪这个函数时，似乎 rest 被分解成它的最后一个元素，然后只 return 一直返回最后一个元素。

我完全看不出在递归调用后修改 current 变量对 return 值有什么影响。

我已经多次跟踪这个函数，下面是一个例子：

假设 Node in = 1 和 in.next = 2

痕迹似乎如下：

reverse(in) (in is currently 1 , 2)

in 现在被称为 current 从现在开始：

rest = reverse(current.next) which is equivalent to: rest = reverse(2) 其中 returns 2 通过基本案例

现在rest = 2

current.next.next = 当前

这使得 current = 1 , 2 , 1 , 2 ???

current.next = null 设置 current = 1

function returns rest which is equal to 2 没有 .next 我可以看到的值，因为它没有在任何地方被修改，但是当我测试这个 [=29= 的输出时]

那么如何正确交换剩余部分？

我觉得我没有捕捉到的变量之间似乎存在某种引用，因为没有 rest.next

的声明

有人介意帮我解决这个问题吗？

看起来很简单，但一直到现在都想不通。不过，此功能可以正常工作。看来我的痕迹在告诉我如何做方面效率低下。

Answer 1

你 return 无论递归调用有什么 returned，不变。递归调用 return 编辑了什么？链表中的最后一个节点。

很自然地，最后一个节点成为反向列表中的第一个。

保存 return 值后的最后几行处理将当前节点链接到反向列表的 currently last 节点，这是你的 下一个，在那一刻

重新链接完成后，您可以return现在完全反转列表的头部：

curr ->   next  ->  ....    -> last 
curr ->   next  ->  ... <- ... last
curr ->   <- next   ... <- ... last
. <- curr <- next   ... <- ... last

递归函数的每次调用都在单独的 堆栈框架 上维护它自己的一组函数内部变量。示例：

reverse( {101= val:1 next:102}, {102= val:2 next:103}, {103= val:3 next:null} )

                    => reverse( {102= val:2 next:103}, {103= val:3 next:null} )

                                          =>  reverse( {103= val:3 next:null} )
                                          |            curr                    curr.next == null
                                         <= {103}
                    |- - - - - - - - - - - - - - - - - - - - - - - - - - - -   curr == 102
                    |           curr                   curr.next               curr.next == 103
                    |                                  {103= val:3 next:102}   curr.next.next = curr
                    |           {102= val:2 next:null}                         curr.next = null
                   <= {103}
   |- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -  curr == 101
   |     curr                    curr.next                                     curr.next == 102
   |                             {102= val:2 next:101}                         curr.next.next = curr
   |     {101= val:1 next:null}                                                curr.next = null
  <= {103}

current.next = null 行代码只在最后一次调用时才需要，它与原始列表的第一个节点一起工作。它可以在所有其他调用中跳过，但这将需要更多代码来安排，并且会使临时列表处于不连贯的状态。

Answer 2

举个例子，假设我们的列表有 2 个项目，1 & 2 其中 1 位于最前面，它们的开头有这些值：

1
Value = 1
Next = 2

2
Value = 2
Next = null

您调用 reverse(1) 并在该上下文中（让我们按递归深度和嵌套对其进行标记）：

R1
Current = 1
  R2
  Current = 2
  (return 2)
Rest = 2
Current ₍₁₎ .next ₍₂₎.next _{(null before assignment)} = Current ₍₁₎    | So now 2.next == 1
Current ₍₁₎ .next ₍₂₎ = null                                                          | So now 1.next == null
(return Rest _{(which is 2)})

现在，如果在 1 之前还有另一个项目，当该项目被处理时，它会设置 1 的 next 自身，就像上面的例子一样，1 将 2 的 next 设置为自身。

Answer 3

这是可行的，因为变量是对您的对象的引用，而不是当前对象。

举个例子（这并不是为了遵守任何程序语言语法）：

objects = {e1, e2, e3};
e1.next = e2; e2.next = e3; e3.next = null;

此时，e1.next和e2.next是对存在于内存中的正确对象的引用，而e3.next是null，在这种情况下没有对象被引用.

而不是x是对y的引用，我会说x点y，使解释更紧凑和简单。不管怎样，变量是指向对象的指针。我还使用了 2 个空格来缩进，这样行就不会那么长了。

然后你调用reverse(e1)，我们打开递归，每一行解释：

reverse(e1); // current points e1
{
  if(current == null || current.next == null) // false
  {
    return current; // not executed
  }
  Node rest = reverse(current.next); // recursion, here current points e2
  {
    if(current == null || current.next == null) // false
    {
      return current; // not executed
    }
    Node rest = reverse(current.next); // recursion, here current points e3
    {
      if(current == null || current.next == null) // true
      {
          return current; // returns current that points e3
      }
      current.next.next = current; // not executed
      current.next = null; // not executed
      return rest; // not executed
    } // end of recursion
    // now rest points e3 (the "if" above was true, returning current)
    // current is e2 again
    current.next.next = current; // e2.next.next (this is e3.next) = e2
    current.next = null; // e2.next points nothing
    return rest; // return e3 (rest points e3)
  } // end of recursion
  // now rest points e3
  // current points e1 again
  current.next.next = current; // e1.next.next (this is e2.next) = e1
  current.next = null; // e1.next points nothing
  return rest; // return a pointer to e3
}

因此，您得到 e3、e3.next = e2、e2.next = e1 和 e1.next = null。

注意递归数是列表中对象的数量减1，所以如果一个列表有1000个元素，堆栈将被1000次调用填充（一次正常程序调用和999次连续递归）。对于内存较小的小型设备，这可能是个大问题（可能是 20 个元素是个问题），但我从来没有必要担心 PC 上的堆栈大小。

对这个链表的递归逆向器中的 return variable/value 感到困惑

Confused about return variable/value in this recursive reverser of a linked list

java

recursion

linked-list