c++ - 以下递归程序的最后一行是如何工作的？

Question

我在研究链表，然后我找到了一个递归反转链表的代码。这是 C++ 代码。

void recursiveReverse(node*& head)
{
  node* first;
  node* rest;

/* checking for an empty list */
  if (head == NULL)
   return;   

  first = head;  
  rest  = first->next;

/* List has only one node */
  if (rest == NULL)
   return;   

  recursiveReverse(rest);
  first->next->next  = first;  
  first->next  = NULL;          

/* fix the head pointer */
  head = rest;              
}

除了最后一行，我理解了整个代码。因为根据我的说法，rest 指针在递归展开期间也与第一个指针类似地更新，因此，在这段代码的末尾，head 不会指向最后一个节点。

这是我对以下代码的解释。

让我们采用链表 1 -> 2 -> 3。

1. 一开始，first会存放头节点的地址，rest将包含节点 2 的地址。
2. 现在，由于 rest 不为 NULL，因此将调用 recursiveReverse(rest)。
3. 现在，first 将指向节点 2，rest 将指向节点 3。
4. 同样，rest 不为 NULL，因此将调用 recursiveReverse(rest)。
5. 现在，first 将指向节点 3，其余的将包含 NULL。
6. 之后，递归将开始展开，首先返回到节点 2，其余的将返回到节点 3。
7. 现在，声明 first -> next -> next = first; 将导致节点 3 的下一部分指向节点 2，链表将变为 1 -> 2 <- 3。节点 2 的下一部分将包含 NULL，并且由于 head = rest，因此，head 也将指向最后一个节点作为 rest 指针。
8. 之后，first 将指向节点 1，语句 first -> next -> next = first; 将导致节点 2 的下一部分指向节点 1，链表将变成 1 <- 2 <- 3。节点 1 的下一部分将包含 NULL 并且语句 head = rest 将导致头部指向节点 2 而不是节点 3，因为其余部分(第一个 -> 下一个)是目前在节点 2。

谁能解释一下我在解释这段代码时哪里错了？

Answer 1

也许还有其他误解，但我认为基本的误解与您的解释有关“语句 head = rest 将导致 head 指向节点 2 而不是节点 3，因为其余部分(第一个 -> 下一个) 当前在节点 2"。

最后，head 将指向初始列表的最后一个节点。让我们考虑一下您的代码的简化/缩短部分:

rest  = head->next;

if (rest == NULL)  // end of list reached; head points tho the last node 
   return;

recursiveReverse(rest);  // if the end is not reached, go forward with the next node (i.e. the value of head->next

head = rest;    // reset head to the (shared) value of rest. 

这是因为语句recursiveReverse(rest)将被一次又一次地调用，直到head->next为NULL，即结束列表的到达。 recursiveReverse 的最后一次运行返回，因为 head->next == NULL，并且在调用者中，变量 rest 指向最后一个节点。现在请注意，“rest”在所有对 recursiveReverse 的调用中共享，因为它是通过引用传递的。因此，语句 head = rest 将被调用到 recursiveReverse 的每个实例，但是 - 因为 rest 在所有调用中共享并且是在递归调用后没有改变 - 语句 head = rest 将始终将 head 分配给 rest 的相同值，该值仍然指向最后一个节点。

Puh - 希望这是全面的。

无论如何，使用通过引用传递参数的递归函数通常很难理解；通常，当递归函数管理它们的私有(private)状态但使用返回值来协调结果时，事情会变得更容易。如果您安排代码使您拥有 node* reverseRecursive(node *current)，您的代码将变得更容易理解。