【数据结构】反转单向链表的方法之头插法（含原理讲解及代码实现）

将单向链表进行反转的方法很多，这里我们讲解一种比较简单的方法——头插法

目录

为什么头插法要用到三个指针？

第一个指针的用途

第二个指针的用途 

双指针为什么不能反转链表？

 第三个指针的用途

反转链表小结及全过程图示

反转链表代码实现

函数实现

整体项目实现

头文件其他函数

源文件

执行结果

---

为什么头插法要用到三个指针？

可能有的人听过这个方法，听说这个方法要用到三个指针，但是不知道为什么，接下来我会用一道实题，来为大家进行细致的讲解，方便大家明白其中的原理以及代码实现中的一些细节。

例：现有一个单向链表，节点顺序为A->B->C->D->E，请你用某种方法将该链表内节点顺序反转为E->D->C->B->A

首先，我们定义一个结构体，我们将其中的存放的数据命名为val，存放的指针命名为next 

//定义一个结构体
struct node
{
	int val;
	struct node* next;
}List;

第一个指针的用途

既然要反转链表，我们自然要改变next的指向，就这道题而言，我们来实际操作一下，我们来改变一下A中next的指向，我们将A中next的指向改为NULL，该过程如下图所示

第一个问题出现了，由于A的next指向发生了改变，我们无法再找到节点B，链表中其他后续节点的next指向自然也就无法发生改变。

我们需要一个指针，来找到next指向发生改变的节点的后一个节点，以对后续节点进行操作，这句话看着有点绕啊。

举个栗子，在上面这个图中，A里面的next指针的指向发生了改变，我们需要用一个指针，来指向A后面的这个B，在这里我们将这个指针命名为pbehind，如下图所示

自此，第一个指针诞生了！ 

第二个指针的用途 

 接着我们对B中的next指向进行改变，但是第二个问题出现了，B后面只有C、D、E啊，我找不到A啊，那咋办呢？

这时候我们就需要第二个指针了，我们需要他指向即将进行next指向改变的节点的前一个节点

在这道题中，也就是B的指向即将改变，我们需要用一个指针，来指向B前面的A，这里我们将这个指针命名为pfront，如下图所示

自此，第二个指针诞生了！ 

双指针为什么不能反转链表？

 这时候可能有些同学有这种感觉 

 “ 诶，你等会！   我怎么感觉这两个指针就能搞定了啊！”

 那好，我们就用这两个指针来进行一下实际操作，看看是不是真的能完成题目的要求，具体过程如下图所示

 乍一看，这不好得很吗！这博主还非说要用三个指针，真是菜，一点理解都没有

别着急，我写几行伪代码，再给你配几个图，你就知道咋回事了

就拿C到D这段举例吧，一开始链表是这样的

 我们来写几行伪代码，来改变C中next的指向

//令pbehind移动到节点D上
pbehind->next = D;
//断开C与D的链接
C->next = pfront;

 第三个指针的用途

这第三个问题出现了，指针pfront该怎么过去，这时候就会出现这种情况，如下图所示

指针pfront根本就没法过去，pfront指向的是B，而B的next指向的是A，可他要移动到C去，指针pfront被永远的困在了B那里，而我们知道，只靠一个指针是没办法完成链表反转的 

自此，第三个指针诞生了！

 它需要承担起帮助pfront找到被指向的节点，在这个图中，他要做到的就是帮助pfront找到C，这里我们将这个指针命名为ptemp，如下图所示

 接下来，我们再写几行伪代码，来改变C中next的指向

//将节点C中的next指向改为节点B
ptemp->next = pfront;
 
//将pfront通过ptemp移动到节点C上
pfront = ptemp;
 
//将ptemp通过pbehind移动到节点D上
//以在下一次进行节点D的next指向改变,同时下一次能够让pfront移动到节点D上
ptemp = pbehind;
 
//令pbehind移动到节点E上，下一次能够让ptemp移动到节点E上
pbehind->next = E;

 执行完成后得到的结果如下图所示

反转链表小结及全过程图示

我们来粗分一下反转链表的两个步骤：

1. 转向，也就是改变next的指向
2. 三指针平移，先pfront，接着是ptemp，最后是pbehind

自此，反转链表的要求我们已经全部满足了，我们来看一下三指针反转题目中所给链表的全过程，如下图所示

反转链表代码实现

函数实现

PS:大家最好把功能函数写在头文件中，不要写在main函数中，main函数是用来执行功能函数的

int traversal_head_insert(node** pphead)
//这里用到二级指针是因为要改变头节点的位置
{
	//如果该链表为空或者链表中只有一个结点，直接退出
	if (!(*pphead)||(*pphead)->next == NULL)
	{
		return 0;
	}
	//如果链表只有两个结点
	else if ((*pphead)->next->next == NULL)
	{
		(*pphead)->next->next = *pphead;
		(*pphead)->next = NULL;
		return 0;
	}
	//如果链表有大于等于三个节点
	else
	{
        //p1是pfront,p2是ptemp,p3是pbehind
		node* p1 = NULL;
		node* p2 = (*pphead);
		node* p3 = (*pphead)->next;
		while (p3 != NULL)
		{
			//断开转向
			(*pphead)->next = p1;
			*pphead = p3;
			//平移三个指针
			p1 = p2;
			p2 = p3;
			p3 = p3->next;
		}
		//当p3==NULL时，说明链表中只有两个节点未进行反转，此时已经不需要再次平移
		//此时p2指向原链表的尾结点
		(*pphead)->next = p1;
		*pphead = p2;
		return 0;
	}
}

整体项目实现

头文件其他函数

#pragma once
#include<iostream>
using namespace std;
 
struct node
{
	int data;
	struct node* next;
}List;
 
//链表初始化(可以有虚拟头节点，有尾结点，头结点)
void List_Create(node** pphead)
{
	node* ptemp = NULL;
	node* ptail = (node*)malloc(sizeof(List));
	ptail->next = NULL;
	int length;//链表的长度
	cout << "请输入你想要初始化的链表的长度：";
	cin >> length;
	int val;//链表的结点值
	cout << "请依次输入链表中的值：";
	while (length)
	{
		cin >> val;
		ptemp = (node*)malloc(sizeof(node));
		ptemp->data = val; ptemp->next = NULL;//结点的初始化
		if (*pphead == NULL)//如果链表为空，即输入链表的第一个值
		{
			*pphead = ptemp;
		}
		else//如果链表非空
		{
			ptail->next = ptemp;
		}
		ptail = ptemp;//ptail作为尾结点
		length--;
	}
	cout << "链表初始化完成" << endl;
	return;
}
 
 
//链表打印
void list_print(node* phead)
{
	node* pphead = phead;
	cout << "该链表打印结果为:" << endl;
	while (pphead)
	{
		cout << pphead->data << "->";
		pphead = pphead->next;
	}
	cout << endl << "该链表打印完成" << endl;
	return;
}

源文件

#include"List_Function.h"
using namespace std;
 
int main()
{
    //创建一个头节点
	node* phead = (node*)malloc(sizeof(List));
	phead = NULL;
	List_Create(&phead);
	list_print(phead);
	cout << "此时将链表进行翻转" << endl;
	traversal_head_insert(&phead);
	list_print(phead);
}

执行结果

 大家有什么地方没有看懂的话，可以在评论区留言给我，咱要力所能及的话就帮大家解答解答

今天的学习记录到此结束啦，咱们下篇文章见，ByeBye！