第1关：递归创建链表

任务描述
本关任务：用递归方法创建链表。

编程要求
根据提示，在右侧编辑器补充代码，用递归方法创建链表。

测试说明
平台会对你编写的代码进行测试：

测试输入：7 21 51 2 32 0
预期输出：7 21 51 2 32

#include<iostream>
using namespace std;
typedef struct LNode
{
    int data;
    struct LNode* next;
}LNode, * LinkList;
void CreatList(LinkList& p)
{    //递归创建链表
    int n;
    cin >> n;
    if (!n)
        return;
    else
    {
        p = new LNode;
        p->data = n;
        p->next=NULL;
        CreatList(p->next);
    }
}

void Output(LinkList p)
{
    //递归从前向后输出链表
    if (p == NULL) return;
    else
    {
        cout << p->data << ' ';
        Output(p->next);
    }
}
int main()
{
    LinkList L;
    L = new LNode;
    L->next = NULL;
    CreatList(L->next);//递归创建链表
    Output(L->next);
    return 0;
}

第2关：递归从前向后输出链表

任务描述
本关任务：用递归方法从前向后输出链表。

编程要求
根据提示，在右侧编辑器补充代码，递归从前向后输出链表。

测试说明
平台会对你编写的代码进行测试：

测试输入：5 7 6 12 24 0
预期输出：5 7 6 12 24

测试输入：1 0
预期输出：1

void Output(LinkList p)
{    //递归从前向后输出链表
    if (p == NULL) return;
    else
    {
        cout << p->data << ' ';
        Output(p->next);
    }
}//完整代码同上

第3关：递归求解最大值

任务描述
本关任务：用递归方法求解最大值。

编程要求
根据提示，在右侧编辑器补充代码，递归求解最大值。

测试说明
平台会对你编写的代码进行测试：

测试输入：5 12 2 7 32 0
预期输出：32

#include<iostream>
using namespace std;
typedef struct LNode
{
    int data;
    struct LNode *next;
}LNode,*LinkList;
int GetMax(LinkList p)
{    //递归求解最大值
    if (!p->next)
        return p->data;
    else {
        int temp = p->data;
        int nextdata=GetMax(p->next);
        return p->data > nextdata ? p->data : nextdata;
    }
}

void CreatList(LinkList &p)
{
    //递归创建链表
    int n;
    cin>>n; //输入结点数值，输入0则退出
    if (n==0)  p=NULL;
    else
    {
        p=new LNode;
        p->data=n;
        CreatList(p->next);
    }
}
int main()
{
	LinkList L;
    L=new LNode;
    L->next=NULL;
    CreatList(L->next);//递归创建链表
    cout<<GetMax(L->next)<<endl;
    return 0;
}

第4关：递归求解链表的结点个数

任务描述
本关任务：用递归方法求解链表结点个数。

编程要求
根据提示，在右侧编辑器补充代码，计递归求解链表的结点个数。

测试说明
平台会对你编写的代码进行测试：

测试输入：5 27 5 12 32 0
预期输出：5

int GetLength(LinkList p)
{	//递归求解链表的结点个数
    static int n=0;
    if(!p)
        return n;
    else{
        n++;
        GetLength(p->next);
    }
}

或

int GetLength(LinkList p)
{
    if (p == NULL)
        return 0;
    return 1 + GetLength(p->next);
}

第5关：递归求解链表中所有整数的和

任务描述
本关任务：递归求解链表中所有整数的和。

编程要求
根据提示，在右侧编辑器补充代码，用递归方法求解链表中所有整数的和。

测试说明
平台会对你编写的代码进行测试：

测试输入：7 21 51 2 32 0
预期输出：113

int GetSum(LinkList p)
{
    //递归求解链表中所有整数的和
    if(!p->next)
    	return p->data;
    else{
    	return p->data+GetSum(p->next);
	}
}

第6关：递归求解链表中所有整数的平均值

任务描述
本关任务：递归求解链表中所有整数的平均值。

编程要求
根据提示，在右侧编辑器补充代码，用递归方法求解链表中所有整数的平均值。

测试说明
平台会对你编写的代码进行测试：

测试输入：7 21 51 2 32 0
预期输出：22.6

        if(!p->next)	
		return p->data;
	else
	{
		double ave=GetAverage(p->next,n-1);
		return (ave*(n-1)+p->data)/n;
	}

递归返回的结果是剩余链表的平均值，乘以其节点数后，加上当前节点的值，再除以总节点数 n，从而逐步更新当前链表的整体平均值。

第7关：递归逆转链表

任务描述
本关任务：递归逆转链表。

编程要求
根据提示，在右侧编辑器补充代码，用递归方法逆转链表。

测试说明
平台会对你编写的代码进行测试：

测试输入：7 21 51 2 32 0
预期输出：32 2 51 21 7

#include<iostream>
using namespace std;
typedef struct LNode
{
    int data;
    struct LNode *next;
}LNode,*LinkList;
LinkList Reverse(LinkList p)
{
    //递归逆转链表
    // 基本情况：如果链表为空或只剩一个节点，直接返回该节点
    if(p == NULL || p->next == NULL)
    	return p;
    else{
        // 递归情况：逆转剩余的链表，返回新的头节点
    	LinkList newhead=Reverse(p->next);

        // 将当前节点的下一个节点的 next 指针指向当前节点，实现反向连接
    	p->next->next=p;

        // 将当前节点的 next 指针设为 NULL，断开当前节点与后续节点的连接
    	p->next=NULL;

        // 返回新的头节点
    	return newhead;
	}
}
void CreatList(LinkList &p)
{
    //递归创建链表
    int n;
    cin>>n; //输入结点数值，输入0则退出
    if (n==0)  p=NULL;
    else
    {
        p=new LNode;
        p->data=n;
        CreatList(p->next);
    }
}
void Output(LinkList p)
{
    //递归从前向后输出链表
    if (p==NULL) return;
    else
    {
        cout<<p->data<<' ';
        Output(p->next);
    }
}
int main()
{
	LinkList L,H;
    L=new LNode;
    L->next=NULL;
    CreatList(L->next);//递归创建链表
    H=Reverse(L->next);//递归逆转链表
    L->next=H;
	Output(L->next);//递归从前向后输出逆转后的链表
    return 0;
}

解释：

1. 基本情况：
   • 当链表为空（p == NULL）或只剩一个节点（p->next == NULL）时，直接返回当前节点作为逆转后的新头节点。
2. 递归情况：
   • 对 p->next 递归调用 Reverse，逆转剩余部分的链表。newHead 保存逆转后的新链表的头节点。
3. 反向连接：
   • 在递归返回时，将当前节点 p 的下一个节点 p->next 的 next 指向当前节点 p，从而实现链表节点的反向连接。
4. 断开连接：
   • 为了避免形成循环，必须将当前节点 p 的 next 指针设为 NULL，断开当前节点与后续节点的连接。
5. 返回新头节点：
   • 最终，返回递归后形成的新的链表头节点 newHead。

参考：单链表的花式反转方法汇总 | labuladong 的算法笔记