一、题目要求
1.1 需求与接口
实现函数List Reverse( List L )，输入单链表头指针L，返回逆转后的链表头指针。
1.2 数据结构定义
typedef int ElementType; typedef struct Node *PtrToNode; struct Node { // 节点结构：数据域+指针域 ElementType Data; PtrToNode Next; }; typedef PtrToNode List; // List等价于指向节点的指针，代表链表头指针1.3 输入输出样例
- 输入：5 1 3 4 5 2（5 为节点个数，后续数字为各节点数据）
- 输出：1（原链表头节点）；2 5 4 3 1（逆转后的链表）
二、题目分析
2.1 链表结构
题目中链表为不带头节点类型，即头指针L直接指向第一个数据节点，节点间通过Next指针串联，末尾节点的Next为NULL。
以输入样例为例，链表结构可视化：L → 节点1(Data=1, Next→3) → 节点3(Data=3, Next→4) → 节点4→节点5→节点2→NULL
2.2 解题思路
单链表逆转的本质是重新调整节点指针的指向，将每个节点的Next指针从 “指向下一个节点” 改为 “指向前一个节点”。常用两种实现思路：
- 迭代法（头插法）：逐个摘下原链表的节点，将其插入到新链表的头部，最终新链表即为逆转结果。
- 递归法：采用分治思想，先递归逆转当前节点之后的子链表，再调整当前节点与子链表的指针关系。
三、答案及解析
3.1 迭代法（推荐）
List Reverse( List L ){ List p, q; // p为遍历指针，q暂存p的后继节点（防止断链） List newHead = NULL; // 逆转链表的头指针（核心变量） p = L; // 从原链表第一个节点开始遍历 while(p != NULL){ q = p->Next; // 1. 保存p的后继，避免后续操作丢失原链表后续节点 p->Next = newHead; // 2. 将p节点挂到逆转链表的头部 newHead = p; // 3. 更新逆转链表的头指针为p p = q; // 4. p移动到下一个待处理节点 } return newHead; // 返回逆转后的链表头指针 }解析
变量
newHead：始终指向已完成逆转的链表部分的头节点，初始值为NULL（表示逆转链表为空），是整个算法的核心锚点。q：用于暂存p的后继节点，因为修改p->Next后会丢失原链表的后续节点，必须提前保存。p：遍历原链表的指针，逐个处理每个节点。
newHead 的完整变化流程
以输入样例
1→3→4→5→2为例，将newHead的变化与逆转链表状态对应，清晰展示每一步操作：处理节点 newHead 初始值 p->Next = newHead（连接） newHead = p（更新） 逆转链表状态 newHead 的含义 无（初始） NULL - - 空 逆转链表为空 节点 1 NULL 节点 1→Next = NULL newHead→节点 1 1→NULL 逆转链表的头是节点 1 节点 3 节点 1 节点 3→Next = 节点 1 newHead→节点 3 3→1→NULL 逆转链表的头是节点 3 节点 4 节点 3 节点 4→Next = 节点 3 newHead→节点 4 4→3→1→NULL 逆转链表的头是节点 4 节点 5 节点 4 节点 5→Next = 节点 4 newHead→节点 5 5→4→3→1→NULL 逆转链表的头是节点 5 节点 2 节点 5 节点 2→Next = 节点 5 newHead→节点 2 2→5→4→3→1→NULL 逆转链表的头是节点 2 终止与返回当
p=NULL时，说明原链表遍历完成，此时newHead指向原链表的最后一个节点（样例中为节点 2），也就是逆转后链表的头节点，返回newHead即可完成逆转。
3.2 递归法
List Reverse( List L ){ // 终止条件：空链表或只有一个节点的链表，无需逆转直接返回 if (L == NULL || L->Next == NULL) return L; // 1. 递归逆转子链表（处理L->Next开始的部分） List newList = Reverse(L->Next); // 2. 调整当前节点与子链表的指针关系 L->Next->Next = L; // 子链表的末尾节点指向当前节点L L->Next = NULL; // 切断L与原后继的联系，防止链表成环 // 3. 返回逆转后的总链表头（始终是原链表的末尾节点） return newList; }解析
终止条件当链表为空（
L=NULL）或只有一个节点（L->Next=NULL）时，无需逆转，直接返回L，这是递归的出口，避免无限递归。递归核心以样例链表
1→3→4→5→2为例：- 调用
Reverse(L)时，会先递归调用Reverse(3)，Reverse(3)又调用Reverse(4)，直到Reverse(2)触发终止条件，返回节点 2（newList=2）。 - 从最深层递归返回，依次调整每个节点的指针。
- 调用
指针调整
- 当回溯到
Reverse(5)时：L=5，L->Next=2，执行L->Next->Next = L即2->Next=5，再执行L->Next=NULL即5->Next=NULL，此时子链表为2→5→NULL，返回newList=2。 - 继续回溯，依次调整节点 4、3、1 的指针，最终得到逆转链表
2→5→4→3→1→NULL。
- 当回溯到
返回值递归过程中，
newList始终指向原链表的末尾节点（逆转后的头节点），最终返回该节点即可。
)