函数中的分段错误以反转单链表recursivley

Question

我正在实现一个递归反转链表的函数,但是遇到了seg-fault.

typedef struct _node {
   int data;
   struct _node *next;
} Node, *NodeP;

NodeP recursiveReverseList(NodeP first){
   if(first == NULL) return NULL;
   if(first->next == NULL) return first;

   NodeP rest = recursiveReverseList(first->next);
   rest->next = first;
   first->next = NULL;

   return first;
}

你能帮忙吗？

PS迭代版本工作正常.它不是功课.只是练习C.

谢谢你们 :)

Answer 1

一般的递归算法是:

1. Divide2部分列表- 第一个节点和列表的其余部分.
2. 递归调用rest链接列表的反向.
3. 链接rest到first.
4. 修复head指针

你正在正确地做第1步和第2步,但我猜你已经搞砸了第3步和第4步.我建议你试试这个:

NodeP recursiveReverseList(NodeP first){
   if(first == NULL) return NULL; // list does not exist.
   if(first->next == NULL) return first; // list with only one node.

   NodeP rest = recursiveReverseList(first->next); // recursive call on rest.
   //rest->next = first; CHANGE THIS
   first->next->next = first; // make first next to the last node in the reversed rest.

   first->next = NULL; // since first is the new last..make its next NULL.

   //return first; CHANGE THIS
   return rest; // rest now points to the head of the reversed list.
}

图片http://geeksforgeeks.org/wp-content/uploads/2009/07/Linked-List-Rverse.gif.

编辑:

PS:我没试过这个.所以尝试一下,让我们知道:)

我测试了上面的功能,似乎按预期工作.您可以在此处试用该程序:http: //ideone.com/bQXAV