通过递归颠倒链表的困惑？

Question

可能重复：
Linked list recursive reverse

我搜索了我的问题，并获得一个链接

recursion stack trace

我din't明白是怎么head_ref指向4在那里？

任何人都可以帮助我理解这一点吗？

Answer 1

确定，首先，它的6个在这里，我不能整夜睡不着......所以这可能是废话）......但在这里，我们去：

“神奇”发生在recursiveReverse(&rest); ... &说，参数是休息地址...因为休息本身是一个指针，我们的参数是一个指针指针...

当函数完成时，指针有并且指向颠倒子列表（它是4节点）的第一个元素...

EX：

让我们说，我们有我们的名单1 - > 2 - > 3 - > 4，并呼吁recursiveReverse(struct node** head_ref)的指针的指针1节点作为head_ref参数

让我们说head_ref处于某些地址（我称之为A）

head_ref是一个指针的指针......这样的地址A的值是另一个地址（我们称之为B）

所以“事”存储在B是一个指针...所以在B的值也是一个地址（我们称之为地址C）

终于“一事一议”存储在C是我们的结构...

考虑到这一点，现在

，我们做我们的第一个递归调用recursiveReverse(struct node** head_ref) ...这个时候我们的参数&休息...... &剩下的就是指向双节点的指针...

让我们仔细看一下...... &的值是一个地址......（很难猜到，我们称之为D）......值在D是我们调用的地址（双节点的地址）E

递归调用完成后，子列表2→3→4已经颠倒过来（4-> 3-> 2）和我们的一个地址已更新为新的值... D已更新，并且不再保留地址E，而是4节点的地址（如果您想要，则调用F即可）...

所以现在，我们将指针指向“第一个”指向其下一个指针仍然指向双节点的1-节点...因此使用first->next->next = first，我们纠正了2-节点“下一个”指针，指向1-节点...

由于单节点不再指向双节点，所以我们有first->next=NULL，现在完整的列表已被逆转...

，因为我们没有返回值，我们用指针的指针参数head_ref回报广大逆转列表...与*head_ref = rest

rest是一个指针...它位于地址d ...当前值在d是F（4节点的地址）

所以我们写d的值（其是F，4节点的地址）与地址B（其是* head_ref）

这就是如何返回指向4节点的指针