单链表逆转

一、题目要求

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指针从 “指向下一个节点” 改为 “指向前一个节点”。常用两种实现思路：

1. 迭代法（头插法）：逐个摘下原链表的节点，将其插入到新链表的头部，最终新链表即为逆转结果。
2. 递归法：采用分治思想，先递归逆转当前节点之后的子链表，再调整当前节点与子链表的指针关系。

三、答案及解析

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; // 返回逆转后的链表头指针 }

解析

1. 变量

   • newHead：始终指向已完成逆转的链表部分的头节点，初始值为NULL（表示逆转链表为空），是整个算法的核心锚点。
   • q：用于暂存p的后继节点，因为修改p->Next后会丢失原链表的后续节点，必须提前保存。
   • p：遍历原链表的指针，逐个处理每个节点。

2. newHead 的完整变化流程

3. 以输入样例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

4. 终止与返回当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; }

解析

1. 终止条件当链表为空（L=NULL）或只有一个节点（L->Next=NULL）时，无需逆转，直接返回L，这是递归的出口，避免无限递归。

2. 递归核心以样例链表1→3→4→5→2为例：

   • 调用Reverse(L)时，会先递归调用Reverse(3)，Reverse(3)又调用Reverse(4)，直到Reverse(2)触发终止条件，返回节点 2（newList=2）。
   • 从最深层递归返回，依次调整每个节点的指针。

3. 指针调整

   • 当回溯到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。

4. 返回值递归过程中，newList始终指向原链表的末尾节点（逆转后的头节点），最终返回该节点即可。