递归链表反转代码疑问：为何递归调用后rest值保持不变？

先来看这段递归反转链表的C代码：

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

你的疑问核心拆解 #

你困惑的点在于：为什么最后一次递归调用后rest的值能保持，而且*head_ref = rest能生效？

咱们一步步捋清楚递归过程中的变量逻辑：

1. 每个递归调用确实有自己的first和rest本地副本，但注意recursiveReverse(&rest)传递的是当前层rest变量的内存地址——也就是说，递归子调用里的head_ref指针，指向的是上一层的rest变量本身。当子执行*head_ref = rest时，本质是直接修改了上一层rest的实际值！
2. 拿1 -> 2 -> 3 -> NULL的链表举例子：
   • 第一层递归：first=1，rest=2，调用recursiveReverse(&rest)
   • 第二层递归：first=2，rest=3，调用recursiveReverse(&rest)
   • 第三层递归：first=3，rest=NULL，触发终止条件直接返回
   • 回到第二层：此时子调用已经把当前层的rest更新为3（第三层的*head_ref = rest其实是给第二层的rest赋值），接着执行first->next->next = first（也就是让3的后继指向2），first->next = NULL（让2的后继变为空），最后*head_ref = rest把第一层的rest设为3
   • 回到第一层：rest已经是反转后的子链表头3，执行first->next->next = first（让2的后继指向1），first->next = NULL（让1的后继变为空），最后*head_ref = rest把整个链表的头节点更新为3
3. 关键结论：每次递归子调用的head_ref都关联着上一层的rest变量，子调用完成后会把反转后的子链表头赋值给上一层的rest，回溯时每一层的rest都是已经反转好的子链表头，最终赋值给*head_ref自然就能把整个链表的头更新为反转后的结果。

附上你提供的手写推导图辅助理解：

内容的提问来源于stack exchange，提问作者momo