c++ 实现链表反转
c++ 实现链表反转
　　单向链表的反转是一个经常被问到的一个面试题，也是一个非常基础的问题。比如一个链表是这样的： 1-&2-&3-&4-&5 通过反转后成为5-&4-&3-&2-&1。
　　最容易想到的方法遍历一遍链表，利用一个辅助指针，存储遍历过程中当前指针指向的下一个元素，然后将当前节点元素的指针反转后，利用已经存储的指针往后面继续遍历。源代码如下：
　　struct linka {
　　linka*
　　void reverse(linka*& head) {
　　if(head ==NULL)
　　linka *pre, *cur, *
　　cur=head-&
　　while(cur)
　　ne = cur-&
　　cur-&next =
　　head-&next = NULL;
　　head =
　　还有一种利用递归的方法。这种方法的基本思想是在反转当前节点之前先调用递归函数反转后续节点。源代码如下。不过这个方法有一个缺点，就是在反转后的最后一个结点会形成一个环，所以必须将函数的返回的节点的next域置为NULL。因为要改变head指针，所以我用了引用。算法的源代码如下：
　　linka* reverse(linka* p,linka*& head)
　　if(p == NULL || p-&next == NULL)
　　head=p;
　　linka* tmp = reverse(p-&next,head);
　　tmp-&next =
&&&主编推荐
H3C认证Java认证Oracle认证
基础英语软考英语项目管理英语职场英语
.NETPowerBuilderWeb开发游戏开发Perl
二级模拟试题一级模拟试题一级考试经验四级考试资料
港口与航道工程建设工程法规及相关知识建设工程经济考试大纲矿业工程市政公用工程通信与广电工程
操作系统汇编语言计算机系统结构人工智能数据库系统微机与接口
软件测试软件外包系统分析与建模敏捷开发
法律法规历年试题软考英语网络管理员系统架构设计师信息系统监理师
高级通信工程师考试大纲设备环境综合能力
路由技术网络存储无线网络网络设备
CPMP考试prince2认证项目范围管理项目配置管理项目管理案例项目经理项目干系人管理
Powerpoint教程WPS教程
电子政务客户关系管理首席信息官办公自动化大数据
职称考试题目
就业指导签约违约职业测评
招生信息考研政治
网络安全安全设置工具使用手机安全
3DMax教程Flash教程CorelDraw教程Director教程
Dreamwaver教程HTML教程网站策划网站运营Frontpage教程
生物识别传感器物联网传输层物联网前沿技术物联网案例分析
互联网电信IT业界IT生活
Java核心技术J2ME教程
Linux系统管理Linux编程Linux安全AIX教程
Windows系统管理Windows教程Windows网络管理Windows故障
组织运营财务资本
视频播放文件压缩杀毒软件输入法微博
数据库开发Sybase数据库Informix数据库
&&&&&&&&&&&&&&&
希赛网 版权所有 & &&&&湘教QS2-164&&增值电信业务经营许可证湘B2-当前访客身份：游客 [
当前位置：
发布于 日 11时,
最近学习数据结构，但网上鲜有关于C#的相关代码，因此决定自己整理一套关于数据结构操作的C#语言版代码。&&
本代码采用C#泛型思想和接口建立单链表类，并实现单链表的基本操作，内含控制台版DEMO演示&&
之前发的只包含基本操作的代码分享地址：
代码主要参考的是我学习用到《数据结构（C#语言版）》，但是在实际编写过程中发现了书中代码一些错误的地方，自行进行了更正。&&&
本代码较之前基础版的相比，增加的一些对单链表的操作包括 查找最大数据元素、冒泡排序（升序）、倒置、删除重复元素等。&
如有不正之处，还望各位指出，小生感激不尽！
代码片段(3)
1.&[代码][C#]代码&&&&
/// &summary&
/// 查找单链表中最大的数据元素
/// &/summary&
/// &param name="LL"&被查找的单链表&/param&
/// &returns&返回找到最大的数据元素&/returns&
private static int FindMax(LinkList&int& LL)
// 定义存储数据的变量
int max = -1;
// 判断是否为空表
if(LL.IsEmpty())
Console.WriteLine("单链表中不存在数据元素，无法执行查找操作，操作失败！");
// 执行查找操作
max = LL.Head.D
Node&int& p = LL.Head.N
while (p != null) {
if(p.Data & max)
// 返回查找结果
/// &summary&
/// 对单链表进行冒泡排序（升序）
/// &/summary&
/// &param name="LL"&被排序的单链表&/param&
/// &returns&返回：true=排序成功；false=排序失败&/returns&
private static bool BubbleSort(LinkList&int& LL)
// 判断是否为空表
if(LL.IsEmpty())
Console.WriteLine("单链表中不存在数据元素，无法执行排序操作，操作失败！");
// 执行排序操作
Node&int& node = new Node&int&();
Node&int& p = LL.H
// 开始冒泡排序
while (p != null) {
node = p.N
while (node != null) {
if(p.Data & node.Data)
p.Data = node.D
node.Data =
node = node.N
/// &summary&
/// 将单链表中的元素进行倒置
/// &/summary&
/// &param name="LL"&被倒置的单链表&/param&
/// &returns&返回：true=倒置成功；false=倒置失败&/returns&
private static bool Inversion(LinkList&int& LL)
// 判断是否为空表
if(LL.IsEmpty())
Console.WriteLine("单链表中不存在数据元素，无法执行倒置操作，操作失败！");
/* 通过新建一个单链表的在头部插入元素的方式来实现倒置
* 为了节省资源，使用同一个头结点在逻辑上直接对原单链表进行操作 */
Node&int& p = LL.H
Node&int& node = new Node&int&();
while (p != null) {
p = p.N // 此行代码必须放在操作node之前，否则因为引用传递的关系，node的操作将直接影响到p
node.Next = LL.H
/// &summary&
/// 删除单链表中的重复元素
/// &/summary&
/// &param name="LL"&被操作的单链表&/param&
/// &returns&返回：true=删除成功；false=删除失败&/returns&
private static bool DeleteRepeatElem(LinkList&int& LL)
// 判断是否为空表
if(LL.IsEmpty())
Console.WriteLine("单链表中不存在数据元素，无法执行删除操作，操作失败！");
// 执行删除操作
// 此处使用一个ArrayList来保存已经访问过的值
// 利用IndexOf方法来判断该值是否已存在数组中
// 需要导入命名空间System.Collections
ArrayList arr = new ArrayList();
Node&int& node = LL.H // 该结点保存的值为p的前一个结点
Node&int& p = new Node&int&(); // p 为当前检查是否重复的结点
arr.Add(node.Data);
while (node.Next != null) {
p = node.N
// 判断当前结点的值是否已经保存在arr中，是则说明重复
if(arr.IndexOf(p.Data) == -1)
arr.Add(p.Data);
if(p.Next != null)
node.Next = p.N
// 如果node.next是表最后一个结点，则不需要进行移动，留到循环外处理
if(node.Next.Next != null)
node = node.N
// 跳出循环，处理最后一个结点
// 前面的循环无法处理表最后一个结点，此处进行单独处理
// 处理之前先判断，该链表是否只有一个结点，即node.next已经是null
p = node.N
if(p !=null && arr.IndexOf(p.Data) & -1)
node.Next =
单链表_CSharp（完整版）.zip&~&42KB&&&&
3.&[图片] QQ截图31.png&&&&
开源中国-程序员在线工具：
开源从代码分享开始
无闻的其他代码共有 3232 人关注过本帖
标题：单链表如何倒置？
等　级：新手上路
&&问题点数：0&&回复次数：9&&&
单链表如何倒置？
单链表原地置逆，就是把单链表原地倒置，算法该怎么写那？
搜索更多相关主题的帖子:
等　级：新手上路
帖　子：172
/*对单链表实现就地逆置*/
#include "stdlib.h"
#include "stdio.h"
struct LNode
struct LNode *
typedef struct LN
typedef node *LinkLvoid Inverse(LinkList L)
LinkList ptr,head,
int num,i;
tail=(LinkList)malloc(sizeof(node));
tail-&next=NULL;
printf("\n请输入5个数据:");
for(i=0;i&=4;i++)
scanf("%d",&num);
ptr-&data=
head=(LinkList)malloc(sizeof(node));
head-&next=
printf("逆置后为:");
while(ptr!=NULL)
printf("%d ",ptr-&data);
printf("\n");
void main()
LinkList L;
Inverse(L);
我相信总有一片天空属于我！
等　级：新手上路
帖　子：177
将表头和链表分离，然后将剩下的那些结点按“头插法”依次插入到分离出来的表头上重新组合链表就可以了。
要让一个男人破产，请给他一架相机，要让一个男人倾家荡产，请给他一架望远镜。
等　级：新手上路
帖　子：524
我早就了发了出来。去这里看看
[此贴子已经被作者于 7:10:04编辑过]
生是编程人！！！！死是编程鬼！！！！颠峰人生！！！焚尽编程！！！
爱已严重死机！情必须重新启动！情人已和服务器断开连接！网恋也需要重新拨号！-----激情依旧
等　级：新手上路
帖　子：172
看了，不过比较复杂。
我相信总有一片天空属于我！
等　级：新手上路
帖　子：524
&&& 你的根本就不是逆置。只是头插法罢了。你连逆置的概念都没弄清楚。如果像你那样做。根本就没意义。而且你的只能是5个。。。。。
生是编程人！！！！死是编程鬼！！！！颠峰人生！！！焚尽编程！！！
爱已严重死机！情必须重新启动！情人已和服务器断开连接！网恋也需要重新拨号！-----激情依旧
等　级：版主
威　望：22
帖　子：715
Node　 *p,*q,*r;
&&p=head-&
&&while(q!=NULL)
&&&q-&link=p;
&&head-&link-&link=NULL;
&&head-&link=p;
这部分就可以实现逆置
c++/C + 汇编 = 天下无敌
等　级：新手上路
能不能用JAVA来写啊？&&
不懂。。。
等　级：论坛游民
专家分：20
void exch(LinkList &L)
&&LinkList p,s;
&&L-&next=NULL;
&&while(p)
&&&&&p=p-&
&&&&&s-&next=L-&
&&&&&L-&next=s;
等　级：新手上路
如链表：L——&&——A——B——C——D——E
倒置第一步有：L——&&——B——A——C——D——E
第二步有：L——&&——C——B——A——D——E
最后又：L——&&——E——D——C——B——A
Status DaoZhi(LinkList &L){
&&& LinkList p,
&&& pre=p-&
&&& while(pre){
&&&&&&p-&next=pre-&
&&&&&&pre-&next=L-&
&&&&&&L-&next=
&&&&&&pre=p-&
版权所有，并保留所有权利。
Powered by , Processed in 0.027681 second(s), 9 queries.
Copyright&, BCCN.NET, All Rights Reserved数据结构：单链表倒置C/C++算法详细思路（最后有图示）_百度知道
数据结构：单链表倒置C/C++算法详细思路（最后有图示）
希望是能用指针实现的，还有就是我今天看了一天的书了，还是没彻底弄明白，真希望高手能指点迷津~~我把我的积分全给你。
提问者采纳
如果单链表为 head-&a-&b-&c-&d-&e-&NULL 思路就是从head开始逐个指针倒置 head&-a b-&c-&d-&e-&NULL head&-a&-b c-&d-&e-&NULL ... head&-a&-b&-c&-d&-e 算法如下： //假设链表长度大于2 head为第一个结点 p = q = p-& r = q-& p-&next = NULL; while(r != NULL) { q-&next = //这里就是倒置p = q= r = r-& } q-&next =
提问者评价
谢谢你们对我的帮助，非常感谢
其他类似问题
为您推荐：
其他1条回答
这个很简单, 对于单链表来说。 head是头指针， while (head != NULL && head-&next != NULL) { pnext = head-&// pbak = pNext-& pnext-&next = head = pnext = } 这就实现了倒转, head是原来是第一个节点，现在成了最后一个。 这只是写程序最简单的基本功， 希望楼主多多加强基础。
您可能关注的推广
单链表的相关知识
等待您来回答
下载知道APP
随时随地咨询
出门在外也不愁1023人阅读
反转单链表
& & & & 定义一个函数，输入一个链表的头结点，反转该链表并输出反转后链表的头结点。链表结点定义如下：
& & & & struct node
& & & & & & & &&
& & & & & & & & struct node *pN
#include &stdio.h&
#include &stdlib.h&
struct node
struct node *pN
struct node *gen()
struct node *pHead = NULL;
for(int i = 10; i & 0; i--){
struct node * p = (struct node *)malloc(sizeof(struct node));
p -& val =
p -& pNext = pH
void display(struct node *pHead)
while( pHead != NULL)
printf(&%d &, pHead-&val);
pHead = pHead-&pN
printf(&\n&);
//递归实现
struct node * reverse(struct node *pHead)
if (pHead == NULL || pHead -& pNext == NULL)
struct node *p = pHead -& pN
struct node *pNewHead =
reverse(p);
p -& pNext = pH
pHead -&pNext = NULL;
return pNewH
//尾递归实现
struct node * do_reverse_tail(struct node *pHead, struct node *pNewHead)
if(pHead == NULL)
return pNewH
struct node *pNext = pHead-&pN
pHead-&pNext = pNewH
return do_reverse_tail(pNext, pHead);
struct node * reverse_tail(struct node *pHead)
return do_reverse_tail(pHead, NULL);
//迭代实现
struct node * reverse_it(struct node *pHead)
struct node *pNewHead = NULL;
struct node *pPrev = NULL;
struct node *pCur = pH
while(pCur != NULL)
struct node *pTmp = pCur-&pN
if(pTmp == NULL)
pNewHead = pC
pCur-&pNext = pP
pPrev = pC
return pNewH
int main()
struct node *pHead = gen();
display(pHead);
pHead = reverse_it(pHead);
display(pHead);
版权声明：本文为博主原创文章，未经博主允许不得转载。
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：31904次
排名：千里之外
原创：45篇
(3)(4)(1)(1)(13)(21)(2)