程序填空题：逆转单链表（递归法）
逆转单链表（递归法）
```c++
#include
using namespace std;
typedef int ElemType;
typedef struct LNode {
ElemType data;
struct LNode *next;
} LNode, *LinkList;
void CreateList(LinkList &L, int n) {
LinkList p, r;
int length;
L = new LNode;
cin >> L->data;
L->next = NULL;
r = L;
length = 1;
while (length p = new LNode;
cin >> p->data;
p->next = NULL;
r->next = p;
r = p;
length++;
}
}
void print(LinkList L)
{
LinkList p;
int flag=1;
p = L;
while (p) {
if(flag)
cout << p->data;
else
cout << " "<< p->data;
flag=0;
p = p->next;
}
}
LinkList reverse(LinkList L)
{
LinkList p;
if(@@[L==NULL||L->next==NULL](2))
return L;
@@[p=reverse(L->next)](2);
L->next->next=L;
L->next=NULL;
@@[return p](2);
}
int main() {
LinkList L;
ElemType e;
int length;
cin >> length;
CreateList(L, length);
L=reverse(L);
print(L);
return 0;
}
```
答案：
第1空：L==NULL||L->next==NULL
第2空：p=reverse(L->next)
第3空：return p
```c++
#include
using namespace std;
typedef int ElemType;
typedef struct LNode {
ElemType data;
struct LNode *next;
} LNode, *LinkList;
void CreateList(LinkList &L, int n) {
LinkList p, r;
int length;
L = new LNode;
cin >> L->data;
L->next = NULL;
r = L;
length = 1;
while (length
cin >> p->data;
p->next = NULL;
r->next = p;
r = p;
length++;
}
}
void print(LinkList L)
{
LinkList p;
int flag=1;
p = L;
while (p) {
if(flag)
cout << p->data;
else
cout << " "<< p->data;
flag=0;
p = p->next;
}
}
LinkList reverse(LinkList L)
{
LinkList p;
if(@@[L==NULL||L->next==NULL](2))
return L;
@@[p=reverse(L->next)](2);
L->next->next=L;
L->next=NULL;
@@[return p](2);
}
int main() {
LinkList L;
ElemType e;
int length;
cin >> length;
CreateList(L, length);
L=reverse(L);
print(L);
return 0;
}
```
答案：
第1空：L==NULL||L->next==NULL
第2空：p=reverse(L->next)
第3空：return p
