帮助理解使用递归反转链表的代码片段
我正在学习 C 中的链接列表考试。我发现自己是一个“审阅者”，它有这段代码。对于我的一生，我无法理解其余的事情是如何逆转的。在这里...它来自 Nick Parlante 先生的《Linked List Problems》（取自斯坦福大学 CIS 图书馆）。 我将添加尼克先生的评论。
RecursiveReverse() 解决方案
也许最难的部分是接受这样一个概念： RecursiveReverse(&rest) 实际上反转了其余部分。然后还有一个技巧 使第一个节点一直到列表的末尾。画个图看看如何 这个伎俩奏效了。
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 elem on the end of the list
first->next = NULL; // (tricky step -- make a drawing)
*headRef = rest; // fix the head pointer
我画了无数的图，
试图追踪正在发生的事情，但我只是无法理解 RecursiveRest(&rest) 实际上如何反转其余部分。请帮忙。我很沮丧。我最终得到的是更小的“休息”......并且没有任何事情是逆转的。 预先非常感谢您。
I am studying for an exam with Linked Lists in C. I found myself a "reviewer" it had this snippet of code. For the life of me, I cannot understand how the rest is reversed. Here it is... it is from Linked List Problems by Mr.Nick Parlante (taken CIS Library, Stanford).
I will put in Mr. Nick's Comments.
RecursiveReverse() Solution
Probably the hardest part is accepting the concept that the
RecursiveReverse(&rest) does in fact reverse the rest. Then then there's a trick
to getting the one front node all the way to the end of the list. Make a drawing to see how
the trick works.
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 elem on the end of the list
first->next = NULL; // (tricky step -- make a drawing)
*headRef = rest; // fix the head pointer
}
I've made countless drawings in attempts to trace what is going on, and I just cannot understand how RecursiveRest(&rest) actually reverses the rest. Please help. I am getting quite frustrated. What I end up getting is smaller "rest"s..and nothing is reversed.
Thank you so much in advance.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
递归通常很难理解，因为很难看出它如何分解为基本步骤。
通常更容易将递归部分视为已经完成并且仅推理组合步骤（这在设计算法时最有用）。
当您尝试可视化递归算法的工作原理时，您必须记住有两个过程在起作用：
这就像一条双向街道。首先，你单向前进，直到解决问题的同时解决最终情况。然后你解决最终的情况。之后，您返回开头，同时合并部分结果。
对于你的情况可能是这样的。请注意，
[AB]表示列表。希望这有帮助。
Recursion is usually hard to comprehend because it's hard to see how it decomposes into basic steps.
It is usually easier to think of the recursive part as already finished and only reason about the combination step (this is most useful when designing the algorithm).
When you are trying to visualize how an recursive algorithm works you have to keep in mind that there are two processes at work:
It's like a two way street. First you go one way until the end case while breaking up the problem. You then solve the end case. After that you return at the beginning while combining the partial results.
For your case it might go like this. Note that
[A-B]means a list.Hope this helps.
当前节点和下一个节点（第一个和
休息）。
工作并反转剩余的列表。
呼叫返回时的最后位置。
所以你只需要检查最后一个
三行代码。
指向第一个（第一个->下一个->下一个=第一个），并且第一个指向
NULL (first->next = NULL)，即从第一个移动到末尾
列表中的。
current and the next node (first and
rest).
works and reverses the remaining list.
last position when the call returns.
So you just have to check the last
three lines of code.
point at first (first->next->next = first), and first points to
NULL (first->next = NULL), i.e. you move first to the end
of the list.