C语言 标记对链表尾部的头部引用

Question

反转链表的迭代方法是非常简单的方法。我试图通过以下链接来理解递归方式

http://www.geeksforgeeks.org/write-a-function-to-reverse-the-nodes-of-a-linked-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;              
}

我们首先将指针移动到链表的尾部。在堆叠展开过程中，我们会反向缝合链接。但是对于所有堆栈展开调用， *headref = rest .因此，由于第一个在堆栈展开过程中更改为以前的堆栈值，为什么其余部分也没有更改。我创建了 4 个节点并通过 gdb 查看值。堆栈展开期间的其余值保持不变，但第一个值正在发生变化。为什么休息不改变。

Answer 1

虽然从改变指针和值的角度思考是一个很好的方法考虑迭代程序，这是一种令人困惑的看待方式递归程序，因为每个递归调用都会创建自己的本地变量，所有变量的名称都相同，但可能具有不同的值。

使用递归函数，假设它对大小为 n 的输入工作正常，然后验证其大小为 n+1 的输入的正确性会更有帮助。如果覆盖了"基本情况"（大小 0 或 1），则证明它适用于所有输入

在您的情况下，假设 recursiveReverse 适用于长度为 3 的列表，让我们a->b->c->d在哪里打电话recursiveReverse(&p) p=a

first->next 和 rest 都将是b的，因此指向一个 3 元素列表b -> c -> d，所以（根据我们的假设） recursiveReverse(&rest)将正确反转此列表。之后调用，rest已更改值（从 b 更改为 d），现在指向此反向列表d->c->b

first->next仍然是与调用前相同的指针b，因此现在指向列表的末尾。因此，first->next->next = first将first附加到此反向列表的末尾，然后变为d->c->b->a ）由于first现在是列表的末尾，我们现在需要first->next = NULL . 最后一步是更改*head_ref（从a更改为d），因此，从recursiveReverse(&p)回来后，p将从a变为新的列表负责人，d。

这表明每当函数对 n 元素正常工作时列表，它适用于 n+1 元素列表。基本情况很容易，因此，已经表明它适用于所有列表。

现在，为什么在调试器中看不到rest变化的值？因为它的值仅由函数调用更改 recursiveReverse(&rest) . 递归调用之前 recursiveReverse它有一个值，则从它返回后它具有另一个，在单步执行和退出每个函数调用时，您看不到它的变化。更改其值的赋值实际上是函数返回之前的最后一个（*head_ref = rest），但在此堆栈帧中调用 head_ref asignee，而不是rest（因为它在调用者的堆栈帧中被调用）

这就是我上面提到的"相同名称，但不同价值观"的混淆。