使用递归算法反转链表
Reversing Linked List using recursion algorithm
我无法理解反转链表的算法如何修复头指针。
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;
/* reverse the rest list and put the first element at the end */
recursiveReverse(&rest);
first->next->next = first;
/* tricky step -- see the diagram */
first->next = NULL;
/* fix the head pointer */
*head_ref = rest;
}
前面的都懂了,就是最后一句没听懂。
如果列表是1->2->3。所以,recursiveReverse(2) 将设置 *head_ref 为 3。但是当它 returns 到 recursiveReverse(1) 时,这里 rest 指向 2。所以不应该设置 *head_ref 到2,(这是不正确的)但实际上并非如此。这是如何工作的?
当调用 recursiveReverse(2) 时,recursiveReverse(1) 正在传递一个 reference 到 recursiveReverse(2) 修改为指向 3 的 rest。然后当 recursiveReverse(1) sets *head_ref = rest;
rest 实际上指向 3.
另一种解释。在递归调用之前的代码中,在倒数第二个嵌套调用中,rest 被设置为指向最后一个节点,而在最后一个调用中,rest 被设置为列表末尾的 NULL,但在这种情况下函数 returns 没有更新 head_ref==rest,所以在 recursiveReverse 的第二个 return 之后,rest 指向最后一个节点,并且永远不会再次更新。 "tricky step" 没有那么棘手,如果是嵌套调用,那么当 recursiveReverse returns 时,first->next->next 会覆盖它。如果是初始调用,则第一个节点的下一个指针设置为空。评论版本:
void ReverseList(NODE**a)
{
NODE *list; /* will be pointer to reversed list */
/* NULL check */
if(a == NULL || *a == NULL)
return;
/* recurse until last node is reached */
list = (*a)->next;
if (!list)
return;
ReverseList(&list);
/* list now points to what was last node */
/* reverse a next pointer */
(*a)->next->next = *a;
/* set current end of reversed list */
/* next gets over written if nested call */
(*a)->next = NULL;
/* set pointer to start of reversed list */
*a = list;
}
return使用指针而不是使用双指针的替代版本:
NODE * ReverseList(NODE*a)
{
NODE *list; /* will be pointer to reversed list */
/* NULL check */
if(a == NULL)
return NULL;
/* recurse until last node is reached */
list = a->next;
if(list == NULL)
/* return pointer to last node */
return a;
list = ReverseList(list);
/* list now points to what was last node */
/* reverse a next pointer */
a->next->next = a;
/* set current end of reversed list */
/* next gets over written if nested call */
a->next = NULL;
/* return pointer to what was last node */
return list;
}
我无法理解反转链表的算法如何修复头指针。
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;
/* reverse the rest list and put the first element at the end */
recursiveReverse(&rest);
first->next->next = first;
/* tricky step -- see the diagram */
first->next = NULL;
/* fix the head pointer */
*head_ref = rest;
}
前面的都懂了,就是最后一句没听懂。
如果列表是1->2->3。所以,recursiveReverse(2) 将设置 *head_ref 为 3。但是当它 returns 到 recursiveReverse(1) 时,这里 rest 指向 2。所以不应该设置 *head_ref 到2,(这是不正确的)但实际上并非如此。这是如何工作的?
当调用 recursiveReverse(2) 时,recursiveReverse(1) 正在传递一个 reference 到 recursiveReverse(2) 修改为指向 3 的 rest。然后当 recursiveReverse(1) sets *head_ref = rest;
rest 实际上指向 3.
另一种解释。在递归调用之前的代码中,在倒数第二个嵌套调用中,rest 被设置为指向最后一个节点,而在最后一个调用中,rest 被设置为列表末尾的 NULL,但在这种情况下函数 returns 没有更新 head_ref==rest,所以在 recursiveReverse 的第二个 return 之后,rest 指向最后一个节点,并且永远不会再次更新。 "tricky step" 没有那么棘手,如果是嵌套调用,那么当 recursiveReverse returns 时,first->next->next 会覆盖它。如果是初始调用,则第一个节点的下一个指针设置为空。评论版本:
void ReverseList(NODE**a)
{
NODE *list; /* will be pointer to reversed list */
/* NULL check */
if(a == NULL || *a == NULL)
return;
/* recurse until last node is reached */
list = (*a)->next;
if (!list)
return;
ReverseList(&list);
/* list now points to what was last node */
/* reverse a next pointer */
(*a)->next->next = *a;
/* set current end of reversed list */
/* next gets over written if nested call */
(*a)->next = NULL;
/* set pointer to start of reversed list */
*a = list;
}
return使用指针而不是使用双指针的替代版本:
NODE * ReverseList(NODE*a)
{
NODE *list; /* will be pointer to reversed list */
/* NULL check */
if(a == NULL)
return NULL;
/* recurse until last node is reached */
list = a->next;
if(list == NULL)
/* return pointer to last node */
return a;
list = ReverseList(list);
/* list now points to what was last node */
/* reverse a next pointer */
a->next->next = a;
/* set current end of reversed list */
/* next gets over written if nested call */
a->next = NULL;
/* return pointer to what was last node */
return list;
}