递归反转C中的链表

ajsxfq5m 于 2023-03-07 发布在其他

关注(0)|答案(2)|浏览(151)

给定结构ListNode：

typedef struct _listnode
{
    int item;
    struct _listnode *next;
} ListNode;

如何使用一个返回类型为void的函数和一个参数来传递指向链表头部ListNode的地址，从而递归地反转链表？（注意这个函数不应该有返回类型;反向链表可以从函数外部访问，以便可以打印元素）

void reverseList(ListNode **headptr)
{
    if ((*headptr) == NULL)
        return;

    ListNode *first = *headptr;
    ListNode *rest = first->next;

    if (rest == NULL)
    {
        *headptr = first;
        return;
    }

    reverseList(&rest);

    rest->next = first;
    first->next = NULL;
}

显然，上面的代码只返回了原始列表的第一个元素，而没有被反转，而其余的元素都消失了。

来源：https://stackoverflow.com/questions/75612743/recursively-reverse-a-linked-list-in-c

2条答案

按热度按时间

scyqe7ek1#

函数实现的问题是在这个调用中

reverseList(&rest);

函数更改局部变量rest

ListNode *rest = first->next;

而不是改变数据成员first->next。
在这个if语句中

if (rest == NULL)
{
    *headptr = first;
    return;
}

在函数的前一次递归调用中声明的局部变量被改变了。你需要通过指向头节点的指针将指向原始头节点的指针传递给函数的每一次递归调用。
并且您的函数包含太多的return语句。
该函数的外观如下所示：

void reverseList( ListNode **head )
{
    if (*head && ( *head )->next)
    {
        ListNode *last = *head;

        *head = ( *head )->next;

        reverseList( head );

        last->next->next = last;
        last->next = NULL;
    }
}

赞(0）回复(0）举报 2023-03-07

atmip9wb2#

这些问题：

递归调用将使rest指向原来是列表尾部的节点，因此rest->next = first;是不正确的。rest不再指向原来是第二个节点的节点，但是，您仍然可以通过first->next引用它，因此您可以使用它并编写：

first->next->next = first;

你必须给(*headptr)赋值，使它指向原来的尾部节点，在递归调用之后，你就知道那个节点是什么了：rest指向它，因此使用以下语句结束函数：

*headptr = rest;

NB：没问题，但是您的第二个if块不需要执行*headptr = first;，因为这两个指针已经相等。

赞(0）回复(0）举报 2023-03-07

我来回答

递归反转C中的链表

2条答案

相关问题

热门标签

最新问答