链表递归反向 [英] Linked list recursive reverse
本文介绍了链表递归反向的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!
问题描述
我正在查看下面来自斯坦福图书馆的代码:
I was looking at the code below from stanford library:
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;
}
我不明白的是在最后一个递归步骤中,例如 if list is 1-2-3-4 现在最后一个递归步骤首先是 1,其余的将是 2.所以如果你设置 *head_ref =休息 .. 这使得列表的头部 2 ??有人可以解释一下在反转列表的头部后如何变成 4 吗??
What I don't understand is in the last recursive step for e.g if list is 1-2-3-4 Now for the last recursive step first will be 1 and rest will be 2. So if you set *head_ref = rest .. that makes the head of the list 2 ?? Can someone please explain how after reversing the head of the list becomes 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.
这篇关于链表递归反向的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!
查看全文