使用递归算法反转链接列表

I'm having trouble understanding how the algorithm for reversing the linked list fixes the head pointer.

我无法理解用于反转链表的算法如何修复头指针。

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;              
}

I understood everything before that, its the last line that I don't get.
If the list is 1->2->3. So, recursiveReverse(2) will set *head_ref as 3. But when it returns to recursiveReverse(1), here rest points to 2. So shouldn't that set *head_ref to 2, (which is incorrect) but it doesn't actually. How does this work?

在那之前我理解了一切，这是我没有得到的最​​后一句话。如果列表是1-> 2-> 3。因此，recursiveReverse（2）将* head_ref设置为3.但是当它返回recursiveReverse（1）时，此处rest指向2.所以不应该将* head_ref设置为2，（这是不正确的）但它不会其实。这个怎么用？

2 个解决方案

#1

When recursiveReverse(2) is called, recursiveReverse(1) is passing a reference to rest which recursiveReverse(2) modifies to point to 3. Then when recursiveReverse(1) sets *head_ref = rest; rest is actually pointing at 3.

当调用recursiveReverse（2）时，recursiveReverse（1）传递一个对rest的引用，recursiveReverse（2）修改为指向3.然后当recursiveReverse（1）设置* head_ref = rest;休息实际上指的是3。

#2

An alternative explanation. In the code before the recursive call, in the next to last nested call, rest is set to point to the last node, and in the last call, rest is set to the NULL at the end of the list, but in this case the function returns without updating head_ref==rest, so after the second return from recursiveReverse, rest points to the last node, and is never updated again. The "tricky step" isn't that tricky, if it's a nested call, then when recursiveReverse returns, first->next->next will overwrite it. If it's the initial call, then what was the first node's next pointer is set to null. Commented version:

另一种解释。在递归调用之前的代码中，在最后一次嵌套调用中，rest被设置为指向最后一个节点，而在最后一次调用中，rest被设置为列表末尾的NULL，但在这种情况下，函数返回而不更新head_ref == rest，所以在从recursiveReverse返回第二个之后，rest指向最后一个节点，并且永远不会再次更新。 “棘手的步骤”并不是那么棘手，如果它是嵌套调用，那么当recursiveReverse返回时，first-> next-> next将覆盖它。如果是初始调用，那么第一个节点的下一个指针是什么设置为null。评论版：

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;
}

alternate version that returns a pointer rather than use a double pointer:

返回指针而不是使用双指针的备用版本：

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;
}