时间戳

首页 > 解决方案 > 递归反向链表

c - 递归反向链表

问题描述

我很难理解这个递归代码是如何工作的，我已经绘制了图纸并通过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}

继续执行代码到 hit 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 和 line 之后rest = first->next;，被执行rest指向节点 2。

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

为什么本地状态丢失并且休息点指向节点 3？

标签： crecursionlinked-listreversesingly-linked-list

解决方案

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

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

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

所以节点的数据成员nextfirst指向，first_of_rest而节点的数据成员next first_of_rest“指向”nullptr。

所以此时我们需要做的是设置节点的数据成员first_of_rest指向节点first 

first->next->next = first;

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

first->next = NULL;

因此我们有

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

推荐阅读