4

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

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

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;    
}
4

2 回答 2

3

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

基本上你在做：

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

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

此外，您malloc被浪费了并且会导致内存泄漏：您分配给一个新的内存块，然后当您在下一行nextNode分配其他内容时丢失对该块的引用： A在这里是不必要的：您没有添加新的节点到您的列表，仅重新排列您拥有的节点。nextNodenextNode = initial->next;malloc

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

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

于 2012-06-18T21:35:55.333 回答
1

这是为您提供的快速演练：

node *reverse(node *initial){

    if (initial is NULL)
        /* this is an empty list so return */
        return a null pointer;

    if (initial->next is NULL)
        /* this is the recursion base case under normal operation - one elem left */
        return initial;

    node *prev = initial;
    node *nextNode = initial->next;

    /* reverse the rest of the list starting at the next node */
    nextNode = reverse(nextNode);

    /* now just reverse the pointers */
    initial->next->next = prev;
    /*
     * but remember that prev->next still points to the wrong node,
     * we need to clear that 
     */
    prev->next = NULL;

    /* you were also missing the return case here */
    /* we want to keep track of the last element (the new head element) */
    /* keep passing this back up through the recursive steps */
    return nextNode;

}
于 2012-06-19T00:58:10.503 回答