C中通过引用调用链表递归

Question

我正在用C练习链表。我是一个初学者，两周前才开始学习C。

我非常理解链表的概念，我试图用递归来反转一个链表。

我知道如何使用while循环反转它，但是在递归中，我被卡住了如何将头指针指向最后一个数字地址，而不是在我反转列表后的初始第一个数字地址。

下面是我的逆函数。头部是在main中定义的，我在函数中通过引用调用它。我知道我可以通过按值调用它来解决这个问题，只需在main()中写入head=reverse(node* head);或者在动态内存中定义head然后直接从函数中访问它。我不想那么做。我想通过main和返回void的函数的引用来调用它。

这是我的反向函数:

void reverse(struct node** head)
{   
    struct node* p=*head;

    if(p->link==NULL)
    {  *head=p;
        return;
    }
    reverse(&(p->link));
    p->link->link=p;
    p->link=NULL;

}

说列表是:5 6 7 2 3 4反向后我得到的输出是:5我知道原因是因为头仍然指向第一个数字地址。我想不出怎么把它指向最后一个数字地址。它应该在if语句中这样做当它破坏递归函数时。但这行不通。

谢谢!

Answer 1

新的头节点是旧的尾节点。旧的尾巴只在基本情况下是已知的，这是递归的最深层，在那里没有任何东西可以进一步递归。因此，您有两种选择:通过整个调用堆栈的引用使原始头可用，以便基本情况可以重新分配它，或者将旧尾返回到调用堆栈中，以便在顶层可以进行重新分配。