gpt4 book ai didi

c - 递归反向链表

转载 作者:行者123 更新时间:2023-12-05 01:18:53 25 4
gpt4 key购买 nike

我很难理解这个递归代码是如何工作的,我画了图并通过 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?

最佳答案

假设您有一个列表,它的其余部分已经反转。

在反转其余部分之前,列表具有以下结构

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;

abd 将节点 first 的下一个数据成员设置为“指向”nullptr。

first->next = NULL;

因此我们有

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

关于c - 递归反向链表,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/56406637/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com