递归反向链表

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}，空其余基本情况 if (rest == NULL) 为 true 第一次.

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

这一行执行前，输出在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？

Answer 1

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

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

这里最重要的是在递归调用之后，除了第一个元素之外的整个列表都被反转了。

Answer 2

假设您有一个列表，它的其余部分已经颠倒了。

在反转其余部分之前，列表具有此结构

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的下一个数据成员指向first_of_rest，而节点first_of_rest的下一个数据成员"points"指向nullptr。

那么此时我们要做的就是设置节点first_of_rest的数据成员指向节点first

first->next->next = first;

abd 将节点 first 的下一个数据成员设置为 "point" 到 nullptr.

first->next = NULL;

因此我们有

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

递归反向链表

Recursively reverse linked list

c

recursion

reverse

linked-list

singly-linked-list