c - 不理解在 C 中使用递归反转链表的代码片段

Question

void reverse(LIST **head)
{
    if(!*head)
      return ;

    LIST *first=*head,*rest=(*head)->next;
    if(!rest)
      return;

    reverse(&rest);
    first->next->next = first;
    first->next= NULL;
    *head = rest;                                                             
    // printf("   :%d",rest->data);
}

该程序正在运行。上述递归代码用于反转单链表。考虑一个列表 L={1,2,3,4,5} 作为输入。考虑两种情况，情况 1 如果我们取消注释语句 10，输出将是最后一个节点的数据即 5 四次，情况 2 如果我们评论语句号。 09 那么 printf 将打印 5,4,3,2。我的问题是，在情况 1 中，由于这个语句 *head=rest;为什么我们每次调用函数时都会得到rest->data的恒定值？如果我们删除声明号。 09 然后printf将打印rest->data的不同值。
提前非常感谢您。

Answer 1

您没有将first连接到返回列表的尾部(rest)。一种简单的反转方法是使用数组来存储所有元素并以相反的顺序迭代数组 - 就像堆栈一样。

使用递归的另一个选项是从反向返回“尾部”。一旦有了尾部，就可以很简单地首先连接到它并返回它(因为 first 是新的尾部)。

这是使用递归的工作代码:

typedef struct LIST {
    int          data;
    struct LIST *next;
} LIST;

LIST* reverse(LIST **head)
{
    LIST *first, *rest, *tail;
    if (!*head) return NULL;

    first = *head;
    rest = first->next;

    if (!rest) return first; // new tail

    tail = reverse(&rest);
    tail->next = first;
    first->next = NULL;

    *head = rest;                                                             
    return first; // new tail
    // printf("   :%d",rest->data);
}

int main(void) {
    LIST list[5] = { {1, 0}, {2, 0}, {3, 0}, {4, 0}, {5, 0}}; 
    LIST *head = list;
    int i = 0;
    for (; i < 4; ++i) {
        list[i].next = &list[i+1];
    }
    reverse(&head);
    return 0;
}