递归反转链表

Question

我很难理解这个递归代码是如何工作的，我已经画了图并使用 gdb 运行了代码。

void RecursiveReverse(struct node** headRef) 
{
  struct node* first;
  struct node* rest;

  if (*headRef == NULL) return; // empty list base case

  first = *headRef; // suppose first = {1, 2, 3}
  rest = first->next; // rest = {2, 3}

  if (rest == NULL) return; // empty rest base case

  RecursiveReverse(&rest); // Recursively reverse the smaller {2, 3} case
                           // after: rest = {3, 2}

  first->next->next = first; // put the first element on the end of the list
  first->next = NULL;

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

我知道当递归调用栈被建立并且列表只包含{3}时，空的 rest 基本情况 if (rest == NULL) 第一次为真。

---

之后，递归调用栈开始破裂，并且在 {2, 3} 中第一次命中 first->next->next = first;

在执行此行前，在 gdb 中输出:

(gdb)p *first
{data = 2, next = 0x1003001f0}

(gdb) p *rest
{data = 3, next = 0x0} 

执行这行代码后，

(gdb) p *rest
{data = 3, next = 0x1003000a0}

继续执行代码，第二次到达 first->next->next = first; 这一行：

(gdb) p **head_ref
{data = 1, next = 0x1003000a0}

(gdb) p *rest
{data = 3, next = 0x1003000a0} // expected p *rest to be 2

在递归调用堆栈建立时，我期望本地指针rest应该指向节点2，因为**headRef指向节点1，在执行代码rest = first->next;后，rest指向节点2。

执行*headRef = rest;后，headRef不应该指向节点2吗？

为什么本地状态会丢失，rest指向节点3？

- Haslo Vardos

Answer 1

假设您有一个列表，其剩余部分已经被反转。

在反转剩余部分之前，该列表的结构如下：

first -> first_of_rest -> second_of_rest->...->nth_of_rest->nullptr

翻转其余部分后，您将获得

first -> nullptr <- first_of_rest <- second_of_rest <-...<-nth_of_rest
         |                                                      |
         ________________________________________________________
                            the rest part of the list

因此，节点first的数据成员next指向first_of_rest，而节点first_of_rest的数据成员next“指向”nullptr。

因此，我们此时需要做的是将节点first_of_rest的数据成员设置为指向节点first。

first->next->next = first;

将节点first的数据成员next设置为指向nullptr。

first->next = NULL;

因此，我们有

nullptr <-first <- first_of_rest <- second_of_rest <-...<-nth_of_rest

- Vlad from Moscow

---

@HasloVardos 只需考虑列表仅有两个元素的基本情况即可。 - Vlad from Moscow

在反转剩余部分后，当列表看起来像 1->2<-3 且 2->next 包含 null 时，为什么行 *headRef = rest; 不会像它在列表只包含 {2, 3} 时那样将 *headRef 指向节点 2，而是指向了节点 3？在此之后，rest 怎么总是等于 {3,...} 呢？ - Haslo Vardos

所以，只有在基本情况 {2, 3} 中，*headRef = rest 才会实际修改 head 指向 rest rest 等于 3，之后这个赋值操作就变得无关紧要了，因为它做的是同样的事情？ - Haslo Vardos

@HasloVardos 每次调用函数时都会执行最后一个语句，除非头部为空。但是头部始终设置为rest。 - Vlad from Moscow

@HasloVardos 在两个节点的基本情况之后，rest将指向列表的第二个节点，即在调用RecursiveReverse（＆rest）之后; 并且在退出封闭递归调用后不会更改。 - Vlad from Moscow

Answer 2

这是简化的伪代码。它基本上像这样工作：

RecursiveReverse(head):
    if head is empty:
        return
    RecursiveReverse(head->next)

    // When we come here, the whole list except the first
    // element has been reversed. So all that's left to do
    // is to reverse the final step

    head->next->next = head
    head->next = NULL

这里需要认识到的最重要的事情是，在递归调用之后，除了第一个元素以外的整个列表都已经被反转了。

- klutt