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

本文主要是介绍【数据结构】反转单向链表的方法之头插法(含原理讲解及代码实现),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

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

目录

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

第一个指针的用途

第二个指针的用途 

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

 第三个指针的用途

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

反转链表代码实现

函数实现

整体项目实现

头文件其他函数

源文件

执行结果


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

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

上课啦斗图表情包-表情uilhjf-爱斗图

例:现有一个单向链表,节点顺序为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是pbehindnode* 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!

这篇关于【数据结构】反转单向链表的方法之头插法(含原理讲解及代码实现)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/438606

相关文章

hdu1043(八数码问题,广搜 + hash(实现状态压缩) )

利用康拓展开将一个排列映射成一个自然数,然后就变成了普通的广搜题。 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#include<stdlib.h>#include<ctype.h>#inclu

深入探索协同过滤:从原理到推荐模块案例

文章目录 前言一、协同过滤1. 基于用户的协同过滤(UserCF)2. 基于物品的协同过滤(ItemCF)3. 相似度计算方法 二、相似度计算方法1. 欧氏距离2. 皮尔逊相关系数3. 杰卡德相似系数4. 余弦相似度 三、推荐模块案例1.基于文章的协同过滤推荐功能2.基于用户的协同过滤推荐功能 前言     在信息过载的时代,推荐系统成为连接用户与内容的桥梁。本文聚焦于

【数据结构】——原来排序算法搞懂这些就行,轻松拿捏

前言:快速排序的实现最重要的是找基准值,下面让我们来了解如何实现找基准值 基准值的注释:在快排的过程中,每一次我们要取一个元素作为枢纽值,以这个数字来将序列划分为两部分。 在此我们采用三数取中法,也就是取左端、中间、右端三个数,然后进行排序,将中间数作为枢纽值。 快速排序实现主框架: //快速排序 void QuickSort(int* arr, int left, int rig

【C++】_list常用方法解析及模拟实现

相信自己的力量,只要对自己始终保持信心,尽自己最大努力去完成任何事,就算事情最终结果是失败了,努力了也不留遗憾。💓💓💓 目录   ✨说在前面 🍋知识点一:什么是list? •🌰1.list的定义 •🌰2.list的基本特性 •🌰3.常用接口介绍 🍋知识点二:list常用接口 •🌰1.默认成员函数 🔥构造函数(⭐) 🔥析构函数 •🌰2.list对象

【Prometheus】PromQL向量匹配实现不同标签的向量数据进行运算

✨✨ 欢迎大家来到景天科技苑✨✨ 🎈🎈 养成好习惯,先赞后看哦~🎈🎈 🏆 作者简介:景天科技苑 🏆《头衔》:大厂架构师,华为云开发者社区专家博主,阿里云开发者社区专家博主,CSDN全栈领域优质创作者,掘金优秀博主,51CTO博客专家等。 🏆《博客》:Python全栈,前后端开发,小程序开发,人工智能,js逆向,App逆向,网络系统安全,数据分析,Django,fastapi

csu1329(双向链表)

题意:给n个盒子,编号为1到n,四个操作:1、将x盒子移到y的左边;2、将x盒子移到y的右边;3、交换x和y盒子的位置;4、将所有的盒子反过来放。 思路分析:用双向链表解决。每个操作的时间复杂度为O(1),用数组来模拟链表,下面的代码是参考刘老师的标程写的。 代码如下: #include<iostream>#include<algorithm>#include<stdio.h>#

hdu4407(容斥原理)

题意:给一串数字1,2,......n,两个操作:1、修改第k个数字,2、查询区间[l,r]中与n互质的数之和。 解题思路:咱一看,像线段树,但是如果用线段树做,那么每个区间一定要记录所有的素因子,这样会超内存。然后我就做不来了。后来看了题解,原来是用容斥原理来做的。还记得这道题目吗?求区间[1,r]中与p互质的数的个数,如果不会的话就先去做那题吧。现在这题是求区间[l,r]中与n互质的数的和

活用c4d官方开发文档查询代码

当你问AI助手比如豆包,如何用python禁止掉xpresso标签时候,它会提示到 这时候要用到两个东西。https://developers.maxon.net/论坛搜索和开发文档 比如这里我就在官方找到正确的id描述 然后我就把参数标签换过来

让树莓派智能语音助手实现定时提醒功能

最初的时候是想直接在rasa 的chatbot上实现,因为rasa本身是带有remindschedule模块的。不过经过一番折腾后,忽然发现,chatbot上实现的定时,语音助手不一定会有响应。因为,我目前语音助手的代码设置了长时间无应答会结束对话,这样一来,chatbot定时提醒的触发就不会被语音助手获悉。那怎么让语音助手也具有定时提醒功能呢? 我最后选择的方法是用threading.Time

Android实现任意版本设置默认的锁屏壁纸和桌面壁纸(两张壁纸可不一致)

客户有些需求需要设置默认壁纸和锁屏壁纸  在默认情况下 这两个壁纸是相同的  如果需要默认的锁屏壁纸和桌面壁纸不一样 需要额外修改 Android13实现 替换默认桌面壁纸: 将图片文件替换frameworks/base/core/res/res/drawable-nodpi/default_wallpaper.*  (注意不能是bmp格式) 替换默认锁屏壁纸: 将图片资源放入vendo