c - 分配节点(反向链表)

Question

我想编写一种迭代和递归的方式来反转链表。

不幸的是，在这两种情况下，我都遇到了类似的问题:我无法将一个节点的指针更改为另一个节点，并且在某些情况下我很难迭代列表。例如，这是我的递归反向函数:

node *reverse(node *initial){
    node *prev = initial;
    node *nextNode;
    nextNode = (node *)malloc(sizeof(struct node));
    nextNode = initial->next;
    if(nextNode->next == NULL){
        return  prev;
    }
    else{
        nextNode = reverse(nextNode);
        nextNode->next = prev;
    }
}

行 nextNode = initial->next; 使程序崩溃。我确信这段代码还有很多其他问题，虽然如果它存在致命缺陷我愿意接受建议，但我主要只是想解决这个错误以便我可以自己调试其余部分。在迭代版本中，导致程序崩溃的一些类似行是:

startA = startA->next; // startA is a node pointer
backNode = startB; // backNode and startB are both node pointers
backNode->data = frontNode->data; //both ints
frontNode->data = temp; //again both ints

根据要求，其余代码:

main(){
node *  start = buildList();
int i;
int nodeSize = sizeof(struct node);
reverse(start);
}

和构建列表:

node *buildList(){
node *head = NULL;
node *second = NULL;
node *third = NULL;
node *fourth = NULL;
node *fifth = NULL;

head = (node *)malloc(sizeof(struct node));
second = (node *)malloc(sizeof(struct node));
third = (node *)malloc(sizeof(struct node));
fourth = (node *)malloc(sizeof(struct node));
fifth = (node *)malloc(sizeof(struct node));

head->data = 1;
head->next = second;

second->data  =2;
second->next = third;

third->data = 3;
third->next = fourth;

fourth->data =4;
fourth->next = fifth;

fifth->data = 5;
fifth->next = NULL;

return head;    
}

Answer 1

请注意，当您在 if 语句中取消引用 nextNode->next 时，您没有检查 nextNode == NULL。

基本上你在做:

if (initial->next->next == NULL)

如果 initial->next == NULL 会发生什么？这也是您的递归 base-case 的问题。

此外，您的 malloc 被浪费并会导致内存泄漏:您分配给 nextNode 一个新的内存块，然后在分配某些内容时丢失对该 block 的引用else 到下一行的 nextNode: nextNode = initial->next; 这里不需要 malloc:您没有添加新节点到您的列表，只重新排列您拥有的节点。

在实现递归时，请仔细考虑您的基本情况。使用您的代码，您希望递归遍历列表到它的最后一个节点，然后使用 return 再次反向构建列表。您如何知道您何时位于列表中的最后一个节点？这是您的基本情况，您的递归函数应该从这里开始。你能仅使用你的函数参数来确定吗？

这与您当前的代码没有太大区别，但您发布的代码包含许多错误。