帮助理解使用递归反转链表的代码片段

Question

我正在学习C语言中的链接列表考试.我发现自己是一个"评论者",它有这段代码.对于我的生活,我无法理解其余部分是如何逆转的.这是......它来自Mr.Nick Parlante的链接列表问题(采用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)实际上是如何反转其余的.请帮忙.我很沮丧.我最终得到的是较小的"休息"......没有任何事情可以逆转.非常感谢你提前.

Answer 1

递归通常难以理解,因为很难看出它如何分解成基本步骤.

通常更容易将递归部分视为已经完成,并且只考虑组合步骤(这在设计算法时最有用).

当您尝试可视化递归算法的工作方式时,您必须记住有两个进程在起作用:

• 在找到终止案例之前,将原始问题分解为较小的问题
• 解决终止案件
• 结果的组合.

这就像一条双向的街道.首先,在解决问题的同时,直到最后一个案例.然后你解决了最终案例.之后,在结合部分结果的同时返回.

对于你的情况,它可能会像这样.请注意,这[A-B]意味着列表.

[A-B-C-D-E] // RecursiveReverse([A, B, C, D, E])
(A [B-C-D-E]) // this means we are calling RecursiveReverse([B, C, D, E])
(A (B [C-D-E])) // this means we are calling RecursiveReverse([C, D, E])
(A (B (C [D-E]))) // this means we are calling RecursiveReverse([D, E])
(A (B (C (D [E])))) // this means we are calling RecursiveReverse([E]) 
                    // hit the end case and solve it trivially
(A (B (C (D [E])))) // solved
(A (B (C [E-D]))) // and go back while applying the combination case
(A (B [E-D-C])) // combine
(A [E-D-C-B]) // combine
[E-D-C-B-A] // combine

希望这可以帮助.