我正在查看斯坦福图书馆的以下代码:
void recursiveReverse(struct node** head_ref)
{
struct node* first;
struct node* rest;
/* empty list */
if (*head_ref == NULL)
return;
/* suppose first = {1, 2, 3}, rest = {2, 3} */
first = *head_ref;
rest = first->next;
/* List has only one node */
if (rest == NULL)
return;
/* put the first element on the end of the list */
recursiveReverse(&rest);
first->next->next = first;
/* tricky step -- see the diagram */
first->next = NULL;
/* fix the head pointer */
*head_ref = rest;
}
我不明白的是在最后一个递归步骤中,例如如果列表是 1-2-3-4 现在对于最后一个递归步骤,第一个将是 1,其余将是 2。所以如果你设置 *head_ref =休息.. 这使列表的头部 2 ??有人可以解释一下在颠倒列表头部后如何变成 4 吗?
最佳答案
画出堆栈轨迹...
Intial - {1,2,3,4}
Head - 1
Rest = 2,3,4
Recurse(2,3,4)
Head = 2
Rest = 3,4
Recurse(3,4)
Head = 3
Rest = 4
Recurse (4)
Head = 4
Rest = null //Base Case Reached!! Unwind.
So now we pick up
Recurse(3,4)
Head = 3
Rest = 4
// Return picks up here
first->next->next = first;
so list is:
3,4,3
// set head to null,
null ,4,3,
//Off with his head!
4,3
Return
Now we're here
Recurse(2,3,4)
Head = 2
Rest = 3,4
Previous return leaves state as:
Head = 2 //But Head -> next is still 3! -- We haven't changed that yet..
Rest = 4,3
Head->next is 3,
Head->next->next = 2 makes the list (actually a tree now)
4->3->2
^
|
2
And chop off the head leaving
4->3->2
and return.
Similarly, do the last step which will leave
4->3->2->1
^
|
1
and chop off the head, which removes the one.
关于c - 链表递归反向,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/2434411/