代码之家 › 专栏 › 技术社区 › Akshay Parashar

反转链表的递归函数(代码段解释)[已关闭]

code-snippets linked-list recursion algorithm c++

Akshay Parashar · 技术社区 · 8 年前

有人能解释一下下面的代码吗

void reverseList(node **href){
   node *first;
   node *rest;

  if(*href == NULL){
     return;
   }

    first = *href;
    rest = first->next;

    if(rest == NULL){
      return;
    }

   reverseList(&rest);
   first->next->next = first;
   first->next = NULL;


   *href = rest;
}

注意:href是链接列表的标题引用。

我不明白的是最后一句话=> *href = rest 由于这一步将在递归展开时发生,这不会使第二个节点从开始head ref开始,但我们希望最后一个节点作为我们的head ref。

这将如何使最后一个节点成为我们的head\u ref?

1 回复 | 直到 8 年前

molbdnilo 8 年前

reverseList 将更新 *href 因此,它指向了给定列表中的新标题;这是过去最后一个节点。
我认为让你困惑的是,所有的电话都在更新至相同值;当递归调用返回时,它将指向输入的最后一个节点,即结果的第一个节点。
该值仅在递归终止时设置。

我要重新命名 first 和 rest

第一个条件,

if(*href == NULL){
    return;
}

以下内容处理常见的基本情况,在这种情况下,您最终会得到一个单元素列表:

old_head = *href;

/* "If the list has exactly one element, do nothing." */
if(old_head->next == NULL){
    return;
}

然后,递归(请记住,该参数既是“in”参数,也是“out”参数)

new_head = old_head->next;
reverseList(&new_head);

现在,通过递归的力量, new_head 指向颠倒的“列表的其余部分”的开头。
这也是我们的结果的指针。
(尾部的最后一个节点也是整个列表的最后一个节点,对吗?)

我们现在需要的是设置新列表的结尾(在递归过程中,它的初始部分已经反转)。

自从我们救了 old_head 之前,我们可以反转 next 用于跟随它的节点的指针:

old_head->next->next = old_head;
old_head->next = NULL;

就是这个

old_head                                            new_head 
  |                                                    | 
  v                                                    v
+---+    +---+         +-----------------------------+
| ------>|   |  <----- |        reversed             |
|   |    |  ----->     | former continuation of list |
+---+    +---+         +-----------------------------+

变成这样( old_head->next->next = old_head; )

old_head                                             new_head 
  |                                                    |
  v                                                    v
+---+    +---+         +-----------------------------+
| ------>|   |  <----- |         reversed            |
|   |<-----  |         | former continuation of list |
+---+    +---+         +-----------------------------+

然后( old_head->next = NULL; )

old_head                                             new_head 
  |                                                    |
  v                                                    v
+---+    +---+         +-----------------------------+
| X |    |   |  <----- |         reversed            |
| X |<-----  |         | former continuation of list |
+---+    +---+         +-----------------------------+

然后,我们更新参数,以便调用者也获得指向新头部的指针:

*href = new_head;

推荐文章

Matthew Thomas · 在每个决策中给出多个选择的所有可能的决策路径/结果

1 年前

feasega · 聚合物模拟-2个节点之间的最短路线,适用于所有节点

1 年前

Alisa Petrova · 在有向图中更改一对顶点以创建循环

1 年前

Matvey Androsyuk · 如何使用React在树结构中呈现我的组件,就像IDE中的默认文件结构一样

1 年前

Pengcheng · 这个简单的递归函数的输出是什么?你能详细解释一下吗?

1 年前

b39b332d · 使用C++标准库实现高效间隔存储

1 年前

Paul C · 在维基百科上,将二叉搜索树转换为排序链表的算法是否存在错误?

1 年前

ABGR · 二叉树的直径——当最长路径不通过根时的失败案例

1 年前

SHUBHAM KUMAR · 这两个是否完全相同-->“下限(股份有限公司rbegin(),股份有限公司rend(),i,更大<int>())”和“下限(dec.begin(

1 年前

EpicAshman · 数独棋盘程序中同一列和同一行出现两次的数字

1 年前