反向链表的递归函数（代码片段解释）

Question

谁能解释一下下面的代码：

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_ref？

Answer 1

reverseList 将更新 *href 因此它指向给定列表的新头部；这是过去的最后一个节点。
我认为可能会让您感到困惑的是所有调用都将 *href 更新为相同的值；递归调用时returns，会指向输入的最后一个节点，也就是结果的第一个节点。
此值仅在递归终止时设置。

我将重命名 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指向反转的"rest of the list"的头部。
这也是将成为我们结果的指针。
（尾部的最后一个节点也是整个链表的最后一个节点，对吧？）

我们现在需要的是设置新链表的末尾（它的初始部分在递归时已经被反转）

由于我们之前保存了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;

反向链表的递归函数（代码片段解释）

Recursive function to reverse linked list(Code Snippet Explanation)

c++

algorithm

recursion

linked-list

code-snippets