在通过递归逆转链表时是否感到困惑? [英] Confusion in reversing a linked list through recursion?
问题描述
可能重复:
链接列表递归反向
我在SO上搜索了我的问题并获得了链接
I searched my question on SO and got a link
我不明白head_ref是如何指向4的?
I din't understand How the head_ref is Pointing to 4 there?
有人可以帮助我理解这一点吗?
Could anyone help me to understand this?
推荐答案
好的，首先，这里是6点，我整夜无法入睡...所以这可能是胡扯;)...但是我们开始:
ok, first of all, it's 6 am here, and i couldn't sleep all night ... so this might be bullshit ;) ... but here we go:
魔术"发生在 recursiveReverse(& rest); ...表示参数是rest的地址...由于rest本身是一个指针，因此我们的param是指向指针的指针...
the "magic" happens at recursiveReverse(&rest); ... the & says that the parameter is the address of rest ... since rest itself is a pointer, our param is a pointer to a pointer ...
函数完成后，指针已更改，并指向反向子列表的第一个元素(即4节点)...
when the function has finished, the pointer has been changed, and points to the first element of the reversed sub-list (which is the 4-Node) ...
EX:
因此，假设我们具有列表1-> 2-> 3-> 4，并调用了 recursiveReverse(struct node ** head_ref)，该指针指向1节点的指针为head_ref参数
so let's say we have our list 1 -> 2 -> 3 -> 4 and have called recursiveReverse(struct node** head_ref) with a pointer to a pointer to the 1-node as the head_ref parameter
因此，假设head_ref位于某个地址(我称其为A)
so let's say head_ref is at a certain address (which i call A)
head_ref是指向指针的指针...因此，地址A处的值是另一个地址(我们称其为B)
head_ref is a pointer to a pointer ... so the value at the address A is another address (let's call that B)
所以存储在B处的事物"是一个指针...因此B处的值也是一个地址(我们称该地址为C)
so the "thing" that is stored at B is a pointer ... so the value at B is also an address (let's call that address C)
最后，存储在C处的东西"就是我们的结构...
finally the "thing" stored at C is our struct ...
现在考虑到这一点，我们对 recursiveReverse(struct node ** head_ref)进行了第一个递归调用，这次我们的参数是& rest ...& rest是一个指向2节点的指针...
now with this in mind, we make our first recursive call to recursiveReverse(struct node** head_ref) ... this time our parameter is &rest ... &rest is a pointer to a pointer to the 2-node...
让我们仔细看看...& rest的值是一个地址...(很难猜测，我们称其为D)... D处的值是一个地址(2-的地址节点)，我们称之为E
let's have a closer look ... the value of &rest is an address ... (hard to guess, we call that D) ... the value at D is an address (the address of the 2-node) which we call E
在递归调用完成之后，子列表2-> 3-> 4被反转了(4-> 3-> 2)，并且我们的地址之一已更新为新值... D已更新，不再保存地址E，而是保存4节点的地址(如果需要的话，请调用F)
after the recursive call has finished, the sub-list 2 -> 3 -> 4 has been reversed (4 -> 3 -> 2), and one of our addresses has been updated with a new value ... D has been updated, and no longer holds the address E, but the address of the 4-node (call that F if you want ...)
因此，现在，我们有指向第一个节点的指针"first"，而其下一个指针仍指向第2个节点...因此，使用 first-> next-> next =首先，我们更正2节点的"next"指针，使其指向1节点...
so now, we have the pointer "first" pointing to the 1-node which has its next-pointer still pointing at the 2-node... so with first->next->next = first, we correct the 2-nodes "next" pointer, to point at the 1-node ...
由于1节点将不再指向2节点，因此我们有 first-> next = NULL ，现在完整的列表已被颠倒...
since the 1-node shall no longer point to the 2-node, we have first->next=NULL and now the complete list has been reversed ...
因为我们没有返回值，所以我们通过指向指针参数head_ref ...的指针返回反转列表，其中 * head_ref = rest
since we have no return value, we return our reversed list by the pointer to pointer parameter head_ref ... with *head_ref = rest
rest 是一个指针...它位于地址D处... D处的当前值为F(4节点的地址)
rest is a pointer ... it's located at address D ... the current value at D is F (address of the 4-node)
因此我们将D的值(即F，即4个节点的地址)写入地址B(即* head_ref)
so we write the value of D (which is F, the address of the 4-node) to the Address B (which is *head_ref)
这就是返回4节点的指针的方式
and that is how the pointer to the 4-node is returned
这篇关于在通过递归逆转链表时是否感到困惑?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
