c - 在 C 中使用递归反转链表

Question

我正在尝试使用递归反转链表。我在 geeksforgeeks 网站上查看了示例程序。他们玩得很开心explanation 。但我无法理解 *headref 在每次堆栈展开时将保留什么。它不是在每次堆栈展开期间保存下一个地址吗？如果是这样，那么在所有堆栈展开调用期间剩余值如何相同。第一个值在堆栈展开期间发生更改，其余值也是如此。当每次堆栈展开更改第一个值时，为什么剩余值没有更改。请帮忙理解。

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

Answer 1

一旦“剩余列表”在递归步骤中反转，其由 rest 指向的第一个项目就成为其最后一个项目，因此之前的“第一个”将被附加到之后那个。那么它是最后一项，因此它的 next 成员变为 NULL。最后我们通过call参数返回新的head。