c - 递归反转单链表的函数中的段错误

Question

我正在实现一个函数来递归地反转链接列表，但出现段错误。

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

你能帮忙吗？

附注不过迭代版本运行良好。这不是家庭作业。刚刚练习C。

谢谢大家:)

Answer 1

一般的递归算法是:

1. Divide 2中的列表零件 - 首先节点和列表的其余部分。
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.
}

_{(来源:geeksforgeeks.org)}
.

编辑:

PS:我还没有测试过这个。所以尝试一下并让我们知道:)

我已经测试了上述功能，似乎可以按预期工作。您可以在这里尝试该程序: http://ideone.com/bQXAV