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

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

你能帮忙吗？

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

谢谢大家:)

Answer 1

一般的递归算法是：

1. 将列表分为 2 部分 - 首先
节点和列表的其余部分。
2. 递归地调用reverse来获取剩余的
   链接列表。
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

Answer 2

@Unicornaddict 已经发布了正确的算法。

但是，如果您仍然遇到分段错误，我怀疑您在从 main 调用函数时犯了一些错误。

正确：

head->next = recursiveReverseList(head->next);

解释：

• 将 head->next 传递给递归函数。如果你传递head，它会做类似的事情

通话前：
头 --->一个---> B---> C
通话后：
头<--- A <--- B <--- C

这将使 head 指向 NULL 和 A 指向 head 将

• head->next 作为参数传递后，列表的状态为：

头 ---> A <--- B <--- C

所以，你需要让 head 指向 rest (C在这种情况下）。

Answer 3

你的算法似乎是错误的。您需要将指针返回到新列表的头部，但您正在将指针返回到最后一项。

事实上，您可能需要它们两者：指向头部的指针和指向最后一项的指针。

Answer 4

我认为

rest->next = first;

应该是

first->next->next = first;