发帖
雷达卡
目录
方法一：经典迭代法（空间最优）
方法二：递归法
方法三：穿针引线法
方法四：头插法
方法五：数组辅助法
方法一：经典迭代法（空间最优）
迭代法是链表反转的最佳方案（空间复杂度 O(1)、时间复杂度 O(n)），主要思想是使用 3 个指针遍历链表，逐步反转每个节点的方向。
代码如下
ListNode* reverseList(ListNode* head) {
ListNode* prev = NULL;
ListNode* curr = head;
ListNode* nextTemp = NULL;
while (curr != NULL) {
nextTemp = curr->next;
curr->next = prev;
prev = curr;
curr = nextTemp;
}
return prev;
}讲解
步骤1：指针初始化逻辑
ListNode* prev = NULL;
ListNode* curr = head;
ListNode* nextTemp = NULL;prev前驱节点，初始值为
NULLnextNULLprevNULLcurr当前需处理的节点，初始值为原链表头
headnextTemp临时缓存指针，初始值为
NULLcurr->next = prev步骤2：循环遍历核心逻辑（while 循环内）
循环条件
curr != NULL步骤3：保存后继节点
nextTemp = curr->next;示例：原链表
1->2->3->4->5curr=1curr->next=2nextTemp=2这一步是 “保命操作”：如果不保存，后续
curr->nextprevNULL2步骤4：反转当前节点指针
curr->next = prev;关键反转操作：使当前节点的
next示例：首次循环时
curr=1prev=NULL1->next = NULLcurr=2prev=12->next=1步骤5：更新前驱节点
prev = curr;将
prevcurrnextTemp示例：首次循环后
prev=1prev=2步骤 6：更新当前节点
curr = nextTemp;将
currnextTemp示例：首次循环后
curr=2curr=3步骤7：循环结束与返回值
return prev;循环结束条件：
curr == NULL此时
prevprev=5因为所有节点已经反转，原尾节点变为了新链表的首节点，所以返回
prev方法二：递归法
递归法反转链表的核心是从底部向上处理，首先递归至链表尾部找到新的表头，然后从尾部逆向调整每个节点的指针方向。
代码如下
ListNode* reverseList(ListNode* head) {
if (head == NULL || head->next == NULL) {
return head;
}
ListNode* newHead = reverseList(head->next);
head->next->next = head;
head->next = NULL;
return newHead;
}讲解
步骤1：递归终止条件
if (head == NULL || head->next == NULL) {
return head;
}两种终止情况：
- 空链表（
）：直接返回head == NULL
，没有节点需要反转；NULL - 只有一个节点（
）：无需反转，返回该节点本身（此节点将成为最终反转链表的首节点，即原链表的尾节点）。head->next == NULL
作用：递归到达链表最末端时停止，开始 “回溯” 并处理指针反转。
步骤2：递归调用（从上至下，直至链表末尾）
ListNode* newHead = reverseList(head->next);逻辑：不是先处理当前节点，而是优先递归处理
当前节点之后的子链表
。
例：原链表
1->2->3->4->5，调用顺序为：
reverseList(1) → reverseList(2) → reverseList(3) → reverseList(4) → reverseList(5)当递归到达
reverseList(5)时，触发停止条件（
5->next == NULL），返回
5，此时
newHead = 5（这将是最终反转链表的新头部，会持续向上返回）。
步骤3：回溯阶段：调整指针方向
递归调用返回后，进入“回溯”阶段，从链表末尾开始逆向调整指针：
步骤4：使后继节点指向当前节点
head->next->next = head;例：回溯到
reverseList(4)时，
head=4，
head->next=5（此时
5已被返回作为
newHead），执行
5->next = 4，完成
4和
5的反转（原本
4->5变为
5->4）。
再回溯到
reverseList(3)时，
head=3，
head->next=4，执行
4->next=3（原本
3->4变为
4->3），依此类推。
步骤5：断开当前节点与原后继的连接
head->next = NULL;作用：防止形成环状链表。如果不断开，例如在
head=4时，原本的
4->5已更改为
5->4，如果
4->next仍然指向
5，将会形成
4?5的环。
例：
head=4时，执行
4->next = NULL，此时
5->4->NULL，随后回溯到
3时，再执行
4->next=3即可。
步骤6：向上传递新头部
return newHead;无论回溯到哪一层，
newHead始终是原链表的末节点（即反转后的新的头部），通过返回值一路向上传递，最终作为整个函数的结果返回。
方法三：穿针引线法
穿针引线的核心思想是从第二个节点起，依次将节点“头插”到原链表头部，逐步重建反转链表。
代码如下
struct ListNode* reverseList(struct ListNode* head) {
if(head == NULL || head -> next ==NULL){
return head;
}
struct ListNode* curr = head;
while(curr -> next != NULL){
struct ListNode* temp = curr -> next;
curr -> next = temp -> next;
temp -> next = head;
head = temp;
}
return head;
}讲解
步骤1：边界处理
if(head == NULL || head -> next == NULL){
return head;
}空链表（
head == NULL）：没有节点可以反转，直接返回
NULL；
单个节点（
head->next == NULL）：无需反转，返回其本身；
步骤2：初始化当前节点指针
struct ListNode* curr = head;curr始终指向“当前未处理部分的链表头部”，初始为原链表头部
head；
作用：作为固定点，用于定位待头插的节点（
curr->next），并保持未处理部分的连接。
步骤3：核心循环：头插操作四步曲
循环条件
curr->next != NULL：只要
curr后面仍有节点，就继续将其头插至链表头部。
步骤4：保存待头插节点
struct ListNode* temp = curr -> next;例：原链表
1->2->3->4->5，首次循环时
curr=1，
curr->next=2，因此
temp=2；
作用：暂时保存待头插的节点，避免后续操作断开连接后丢失该节点。
步骤5：断开待头插节点与原链表的连接
curr -> next = temp -> next;例：首次循环中，
temp=2，
temp->next=3，执行后
curr->next=3（即
1->3）；
作用：将
curr与待头插节点
temp断开，直接连接到
temp的下一个节点，确保未处理部分的链表不断开。
步骤6：将 temp 节点头插到链表头部
temp -> next = head;例：首次循环中，原
head=1，执行后
temp->next=1（即
2->1）；
作用：使待头插的
temp节点指向当前链表的头部，完成“头部插入”的前置连接。
步骤7：更新表头为 temp
head = temp;例：首次循环后，
head=2，此时链表变为
2->1->3->4->5；
作用：确认
temp成为新的链表头部，完成一次头插操作。
步骤8：循环结束与返回值
return head;循环终止条件：
curr->next == NULL（所有节点都已头插至头部，未处理部分为空）；
此时
head指向原链表的最后一个节点（如例子中的
5），即反转后链表的新头部，直接返回即可。
方法四：头插法
核心是用
dummy作为虚拟头部（初始为
NULL），遍历原链表时将每个节点依次“头插”到
dummy前方，最终
dummy成为反转后链表的头部
代码如下
struct ListNode* reverseList(struct ListNode* head) {
struct ListNode* dummy = NULL;
struct ListNode* cur = head;
while(cur != NULL){
struct ListNode* temp = cur;
cur = cur -> next;
temp -> next = dummy;
dummy = temp;
}
return dummy;
}步骤1：指针初始化逻辑
struct ListNode* dummy = NULL;
struct ListNode* cur = head;dummy：实质是“反转链表的虚拟头部”，初始为
NULL（表示反转链表最初是空的）。主要作用是作为固定点，接收原链表节点的头插，最终成为反转链表的实际头部。
cur：遍历原链表的指针，从原表头
head开始，负责逐一取出节点进行反转操作。
循环条件
cur != NULL：只要原链表还有未处理的节点，就继续头插。
步骤2：保存当前待头插节点
struct ListNode* temp = cur;例：原链表
1->2->3->4->5，首次循环时
cur=1，
temp=1curcur = cur -> next;curtemp->next = dummytemp -> next = dummy;dummy=NULLtemp->next=NULLdummy=1temp->next=1tempdummydummy = temp;dummy=11->NULLdummy=22->1->NULLtempdummyreturn dummy;cur=NULLdummystruct ListNode* reverseList(struct ListNode* head) {
if(head == NULL){
return head;
}
int count = 0;
struct ListNode* curr = head;
while(curr != NULL){
count++;
curr = curr -> next;
}
int* arr = (int*)malloc(sizeof(int) * count);
curr = head;
int i = 0;
while(curr != NULL){
arr[i++] = curr -> val;
curr = curr -> next;
}
curr = head;
for(int k = i - 1; k >= 0; k--){
curr -> val = arr[k];
curr = curr -> next;
}
return head;
}if(head == NULL){
return head;
}head=NULLNULLint count = 0;
struct ListNode* curr = head;
while(curr != NULL){
count++;
curr = curr -> next;
}currcountcurr=NULL1->2->3->4->5count=5int* arr = (int*)malloc(sizeof(int) * count);countfree(arr)curr = head;
int i = 0;
while(curr != NULL){
arr[i++] = curr -> val;
curr = curr -> next;
}currcurr=NULLivali1->2->3->4->5arr = [1,2,3,4,5]i=5curr = head;
for(int k = i - 1; k >= 0; k--){
curr -> val = arr[k];
curr = curr -> next;
}currki-1curr[1,2,3,4,5]5,4,3,2,15->4->3->2->1free(arr); // 补充：释放数组内存，避免内存泄漏
return head;15
京公网安备 11010802022788号
