常用的4种：
- 迭代反转法
- 递归反转法
- 头插法
- 就地逆置法
1 迭代反转法
从当前链表的首元节点开始，一直遍历至链表的最后一个节点，这期间会逐个改变所遍历到的节点的指针域，使其指向前一个节点
1.1 定义 3 个指针并分别命名为 beg、mid、end
遍历链表的过程就等价为：3 个指针每次各向后移动一个节点，直至 mid 指向链表中最后一个节点（此时 end 为 NULL ）。需要注意的是，这 3 个指针每移动之前，都需要做一步操作，即改变 mid 所指节点的指针域，另其指向和 beg 相同。
1.2 先改变 mid 所指节点的指针域指向，另其和 beg 相同，然后再将 3 个指针整体各向后移动一个节点，重复这个操作直到 mid 指向最后一个节点
1.3 此时 mid 已经指向最后一个节点，但还需要最后一次 修改 mid 所指节点的指针域指向，使其和 beg 相同
1.4 最后只需改变 head 头指针的指向，另其和 mid 同向，就实现了链表的反转
迭代反转法的整个过程用 c语言 代码如下：
typedef struct s_node
{
int data;
struct s_node* next;
} Node;
Node* iteration_reverse(Node* head) {
if (head == NULL || head->next == NULL) {
return head;
}
else {
Node* beg = NULL;
Node* mid = head;
Node* end = head->next;
//一直遍历
while (1)
{
//修改 mid 所指节点的指针域指向beg
mid->next = beg;
//此时判断 end 是否为 NULL，如果成立则退出循环
if (end == NULL) {
break;
}
//整体向后移动 3 个指针
beg = mid;
mid = end;
end = end->next;
}
//最后修改 head 头指针的指向
head = mid;
return head;
}
}
伪代码如下：
while (1)
{
mid->next = beg;
if (end == NULL) {
break;
}
beg = mid;
mid = end;
end = end->next;
}
head = mid;
2 递归反转法
递归反转法更适用于反转不带头节点的链表
和迭代反转法的思想恰好相反，递归反转法的实现思想是从链表的尾节点开始，依次向前遍历，遍历过程依次改变各节点的指向，即另其指向前一个节点。
递归反转法的 C语言实现如下：
Node* recursive_reverse(Node* head) {
//递归的出口
//空链或只有一个结点，直接返回头指针
if (head == NULL || head->next == NULL)
{
return head;
}
//一直递归，找到链表中最后一个节点
Node *new_head = recursive_reverse(head->next);
//当逐层退出时，new_head 的指向都不变，一直指向原链表中最后一个节点；
//递归每退出一层，函数中 head 指针的指向都会发生改变，都指向上一个节点。
//每退出一层，都需要改变 head->next 节点指针域的指向为上一个节点head，同时令 head 所指节点的指针域为 NULL。
head->next->next = head;
head->next = NULL;
//每一层递归结束，都要将新的头指针返回给上一层。由此，即可保证整个递归过程中，能够一直找得到新链表的表头。
return new_head;
}
伪代码如下：
Node* recursive_reverse(Node* head) {
if (head == NULL || head->next == NULL)
{
return head;
}
Node *new_head = recursive_reverse(head->next);
head->next->next = head;
head->next = NULL;
return new_head;
}
3 头插法
所谓头插法，是指在原有链表的基础上，依次将位于原链表头部的节点摘下，然后采用从头部插入的方式生成一个新链表，则此链表即为原链表的反转版。
头插法 C语言实现
Node* head_reverse(Node* head) {
Node* new_head = NULL;
Node* temp = NULL;
if (head == NULL || head->next == NULL) {
return head;
}
while (head != NULL)
{
temp = head;
//将 temp 从 head 中摘除
head = head->next;
//将 temp 插入到 new_head 的头部
temp->next = new_head;
new_head = temp;
}
return new_head;
}
伪代码
while (head != NULL)
{
temp = head;
head = head->next;
temp->next = new_head;
new_head = temp;
}
4. 就地逆置法
就地逆置法和头插法的实现思想类似，唯一的区别在于，头插法是通过建立一个新链表实现的，而就地逆置法则是直接对原链表做修改，从而实现将原链表反转。
就地逆置法C语言实现
Node* local_reverse(Node* head) {
Node* beg = NULL;
Node* end = NULL;
if (head == NULL || head->next == NULL) {
return head;
}
// beg 指向第一个节点，end 指向 beg->next
beg = head;
end = head->next;
while (end != NULL) {
//将 end 从链表中摘除
beg->next = end->next;
//将 end 移动至链表头
end->next = head;
// 更新head指向表头
head = end;
//调整 end 的指向，另其指向 beg 后的一个节点，为反转下一个节点做准备
end = beg->next;
}
return head;
}
伪代码
beg = head;
end = head->next;
while (end != NULL) {
beg->next = end->next;
end->next = head;
head = end;
end = beg->next;
}
本文所有代码和例子
//
// LinkListAlgorithm.c
//
// Created by jokerwan on 2020/10/15.
// Copyright © 2020年 jokerwan. All rights reserved.
//
#include "LinkList.h"
#include <stdio.h>
#include <stdlib.h>
// 就地逆置法
Node* local_reverse(Node* head) {
Node* beg = NULL;
Node* end = NULL;
if (head == NULL || head->next == NULL) {
return head;
}
// beg 指向第一个节点，end 指向 beg->next
beg = head;
end = head->next;
while (end != NULL) {
//将 end 从链表中摘除
beg->next = end->next;
//将 end 移动至链表头
end->next = head;
head = end;
//调整 end 的指向，另其指向 beg 后的一个节点，为反转下一个节点做准备
end = beg->next;
}
return head;
}
// 头插法 构造一个新链表，依次位于将原有链表头部节点取下，采用头部插入方式插入到新链表中
Node* head_reverse(Node* head)
{
Node* new_head = NULL;
Node* temp = NULL;
if (head == NULL || head->next == NULL) {
return head;
}
while (head != NULL)
{
temp = head;
//将 temp 从 head 中摘除
head = head->next;
//将 temp 插入到 new_head 的头部
temp->next = new_head;
new_head = temp;
}
return new_head;
}
//递归反转法
Node* recursive_reverse(Node* head)
{
//递归的出口
//空链或只有一个结点，直接返回头指针
if (head == NULL || head->next == NULL)
{
return head;
}
//一直递归，找到链表中最后一个节点
Node *new_head = recursive_reverse(head->next);
//当逐层退出时，new_head 的指向都不变，一直指向原链表中最后一个节点；
//递归每退出一层，函数中 head 指针的指向都会发生改变，都指向上一个节点。
//每退出一层，都需要改变 head->next 节点指针域的指向为上一个节点head，同时令 head 所指节点的指针域为 NULL。
head->next->next = head;
head->next = NULL;
//每一层递归结束，都要将新的头指针返回给上一层。由此，即可保证整个递归过程中，能够一直找得到新链表的表头。
return new_head;
}
//迭代反转法，head 链表的头指针
Node* iteration_reverse(Node* head)
{
if (head == NULL || head->next == NULL)
{
return head;
}
else
{
Node* beg = NULL;
Node* mid = head;
Node* end = head->next;
//一直遍历
while (1)
{
//修改 mid 所指节点的指向
mid->next = beg;
//此时判断 end 是否为 NULL，如果成立则退出循环
if (end == NULL)
{
break;
}
//整体向后移动 3 个指针
beg = mid;
mid = end;
end = end->next;
}
//最后修改 head 头指针的指向
head = mid;
return head;
}
}
//测试四种反转算法
int testReverseLinkList()
{
//创建链表
Node* head = create_list_head();
if(NULL == head)
{
printf("create_list_head failed!\n");
return -1;
}
//填充数据（添加节点）
int i;
for(i=5; i>0; i--)
add_node_head(head, create_new_node(i));
//打印原来链表数据
printf("befor ");
display_list(head);
//反转链表
// head = iteration_reverse(head);
// head = recursive_reverse(head);
// head = head_reverse(head);
head = local_reverse(head);
printf("after ");
display_list(head);
//释放链表空间
free_list(head);
return 0;
}
//创建链表
Node* create_list_head()
{
Node* head = (Node*)malloc(sizeof(Node));
if(NULL != head)
{
head->data= -1;
head->next= NULL;
}
return head;
}
//创建新节点
Node* create_new_node(int node_data)
{
Node* new_node = (Node*)malloc(sizeof(Node));
if(NULL != new_node)
{
new_node->data= node_data;
new_node->next= NULL;
}
return new_node;
}
//打印链表数据
void display_list(Node* head)
{
if(NULL == head)
return;
Node* tmp = head;
printf("list data:");
while(NULL != tmp)
{
printf("%d ", tmp->data);
tmp=tmp->next;
}
printf("\n");
}
//释放链表
void free_list(Node* head)
{
if(NULL == head)
return;
Node* p = head;
while((p = p->next))
{
head->next = p->next;
//printf("free:%d\n", p->data);
free(p);
p = head;
}
free(head);
}
//头插法
int add_node_head(Node* head, Node* new_node)
{
if(NULL == head || NULL == new_node)
return -1;
new_node->next = head->next;
head->next = new_node;
return 0;
}
