使用递归反转单向链表

Question

我已经编写了使用递归反转单向链表的代码。它在长度小于或等于 174725 的列表上运行良好。但是在长度大于174725的列表中，它会给出分割错误(分段错误：11(，同时通过 reverse(( 调用反转它。有人可以向我解释一下吗？

#include <iostream>
using namespace std;
class Node
{
public:
int val;
Node *next;
};
class Sll
{
public:
Node *head;
private:
void reverse(Node *node);
public:
Sll();
void insert_front(int key);
void reverse();
void print();
};
void Sll::reverse(Node *node)
{
if (node == NULL) return;
Node *rest = node->next;
if (rest == NULL)
{
head = node;
return;
}
reverse(rest);
rest->next = node;
node->next = NULL;
return;
}
Sll::Sll()
{
head = NULL;
}
void Sll::insert_front(int key)
{
Node *newnode = new Node;
newnode->val = key;
newnode->next = head;
head = newnode;
return;
}
void Sll::print()
{
Node *temp = head;
while (temp)
{
temp = temp->next;
}
cout << endl;
return;
}
void Sll::reverse()
{
reverse(head);
return;
}
int main()
{
Sll newList = Sll();
int n;
cin >> n;
for (int i = 0; i < n; i++) newList.insert_front(i + 1);
newList.reverse();
// newList.print();
return 0;
}

Answer 1

列表反转函数必须是尾递归的，否则在递归长列表时它会溢出堆栈，就像你观察到的那样。此外，它需要在启用优化或 gcc 选项的情况下进行编译-foptimize-sibling-calls。

尾递归版本：

Node* reverse(Node* n, Node* prev = nullptr) {
if(!n)
return prev;
Node* next = n->next;
n->next = prev;
return reverse(next, n);
}

迭代列表还原可以更容易地内联，并且不需要任何优化选项：

inline Node* reverse(Node* n) {
Node* prev = nullptr;
while(n) {
Node* next = n->next;
n->next = prev;
prev = n;
n = next;
}
return prev;
}