参考链接：

• C语言中文网 - 单链表反转详解
• 力扣 - 单向链表反转

链表节点结构声明：

typedef struct node{
	int a;
	struct node* next;
} Linklist;

Linklist* head;		//指向链表头节点
1
2
3
4
5
6

一、迭代法

1.1 核心思想

  从链表首节点开始，遍历整个链表，逐一将各节点反转为指向前一个节点。

1.2 代码示例

Linklist* reverse1(Linklist* head)
{	
	Linklist *prev = NULL; 
	Linklist *cur = head;
	Linklist *next = NULL;				//节点指针next，不同于结构成员指针next
	while(cur){
		next = cur->next;				//使用next来预留下一个位置
		cur->next = prev;				//指向逆转
		//整体后移
		prev = cur;
		cur = next;
	} 
	head = prev;
	return head;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

• 空链表或单节点链表也包含在其中，无需单独判断；
• 不能使用next =next->next来移动最后一个指针，因为系统无法判断next->next是否为空指针

二、递归法

2.1 核心思想

  从链表的尾节点开始，依次向前遍历，逐个反转。

假设链表为：
n1 → … → n_k-1 → n_k → n_k+1 → … → n_m → Φ

从末尾开始反转，则处于中间时：
n1 → … → n_k-1 → n_k → n_k+1 ← … ← n_m

将 n_k 所在节点反转：n_k.next.next = n_k，且 n₁ 的下一个节点必须为Φ。

2.2 代码示例

Linklist* reverse2(Linklist* head)
{
	//递归出口：空链表或单节点链表
	if(head == NULL || head->next == NULL){
		return head;
	}
	//递进
	Linklist* new_head = reverse2(head->next);		//找到链表尾节点
	
	//回归
	head->next->next = head;		//指向逆转
	head->next = NULL;				//各节点next指向逐级清空
	
	return new_head;				//传回尾节点信息
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

代码说明：
此代码是先调用递归函数，再执行操作，属于在归来的过程中解决问题。（反之是在递进的过程中解决问题）。

• 开始时一直向深层递归（向前递进），直到找到链表尾节点（遇到递归出口），递归终止，然后不断退出；

• 每一次向前递进的过程中，head 都在不断后移（将实参 head->next 赋给形参 head ），那么，在退出递归（即归来）的过程中 head 在不断前移

• 每退出一层递归时，将 head 指向的节点的下一个节点反转为指向 head（head->next->next = head）；
  
  

• head->next = NULL; 保证归来过程中，每一个被反转的节点都不再指向其他节点。目的是最终使n1->next = NULL

• 退出递归时，new_head的值也没有被改变，始终指向原链表的尾节点。且每次都将new_head返回给上一层，保证将尾节点信息（新链表的表头）不断地传递回来。

补充参考链接： 知乎 - 对递归的理解 - 老刘的回答

三、头插法

3.1 核心思想

将原链表的首节点拆下，形成新链表，然后不断拆下原链表的首节点，插入到新链表的头部，原链表拆完后所形成的新链表就是原链表的反转。

3.2 代码示例

Linklist* reverse3(Linklist* head)
{
	if(head == NULL || head->next){
		return head;
	}
	
	Linklist* new_head = NULL;			//创建新链表, 此处必须初始化为NULL
	Linklist* p = NULL;
	//头插
	while(head){
		//拆
		p = head;
		head = head->next;
		//插
		p->next = new_head;
		new_head = p;
	}
	return new_head;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

四、就地逆置法

4.1 核心思想

  在原链表中，假设最初的首节点为节点 p ，不断将 p 其后与之相邻的节点移到链表开头，成为新的首节点，p 相对不断被动后移，直到 p 成为链表尾节点，反转完成。

4.2 代码示例

Linklist* reverse4(Linklist* head)
{
	if(head == NULL || head->next){
		return head;
	}
	
	Linklist* prev = head;
	Linklist* cur = head->next;
	while(cur){
		prev->next = cur->next;			//连接前后，摘除cur节点
		
		//cur节点插入头部
		cur->next = head;
		head = cur;
	
		cur = prev->next;				//更新cur
	}
	return head;	
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

代码说明：

• 最开始的 if判断不可省略，无法与后续代码合并，原因在于当head == NULL时，cur = head->next出现对空指针的引用，将导致未定义行为。