对于不带头结点的单链表L，设计一个递归算法逆置所有结点。编写完整的实验程序，并采用相应数据进行测试。
采用递归方法
思路：设f(L)返回单链表逆置后的首结点指针，为“大问题”，则f(L->next)返回逆置后的首结点指针p,为“小问题”，当小问题解决后，大问题的求解只需要将首结点（L指向它）链接到L->next节点的末尾就可以了。
#include<iostream>
using namespace std;
#define NULL 0
typedef struct node
{
int data;
struct node* next;
}Lnode,*Linklist;
Lnode * reverse(Lnode *L)
{
Lnode * p;
if (L == NULL || L->next == NULL)
return L;
p = reverse(L->next);
L->next->next = L;
L->next = NULL;
return p;
}
int main()
{
Linklist L;
Lnode* q;
L = (node*)malloc(sizeof(node));
L->next = NULL;
q = L;
int n;
cin >> n;
for (int i = 0;i < n;i++)
{
node* p;
p = (node*)malloc(sizeof(node));
cin >> p->data;
q->next = p;
q = p;
q->next = NULL;
}
L = L->next;
L = reverse(L);
while (L != NULL)
{
cout << L->data << " ";
L = L->next;
}
return 0;
}
下面图片更加方便理解
