【链表】C++链表反转、链表逆序打印_逆序输出链表c++-程序员宅基地

技术标签: 算法编程  

转载地址:http://blog.csdn.net/yebanxin/article/details/51942598

题目:C++实现链表逆序打印、链表反转

如何将链表逆序,取决于题目的要求。如果面试官只要求打印,一般不改动链表结构为好,如果要求改变链表的方向,则需要改变结构,再顺序打印。

方法1:只逆序打印,不改变结构。采用递归,到达尾结点时打印输出,否则进入下一个结点的递归,当递归一层层退出的时候,便可以实现从尾到头的打印。

方法2:头插法,改变结构。从第二个结点开始往后,依次把每个结点移至链表头部,要注意最后链表不要是断裂的。

方法3:改变指针方向。从头结点开始,依次把结点的next指针断开指向该结点的前结点。要注意保存好,前结点、当前结点和下一个结点。

方法4:只逆序打印,不改变结构。利用栈的后进先出来实现逆序。


注意:链表为空、链表只有一个结点的情况

完整代码如下:

#include<iostream>
using namespace std;
struct ListNode
{
	int value;
	ListNode *next;
};
void ReversePrint(ListNode *pHead)//递归实现逆序打印(不改变链表结构)
{
	if(pHead!=NULL)
	{
		if(pHead->next!=NULL)
			ReversePrint(pHead->next);
		cout<<pHead->value<<" ";
	}
}
ListNode *ReverseList1(ListNode *pHead)//头插法(改变链表结构)
{
	if(pHead==NULL)
		return NULL;
	ListNode *p=pHead->next;
	ListNode *newHead=pHead;
	while(p!=NULL){			//将p结点移到链表最前方
		pHead->next=p->next;//头结点指向p的下一个结点
		p->next=newHead;	//p插入链表最前方
		newHead=p;		//链表新头结点更新为p
		p=pHead->next;//处理下一个结点,该结点位于头结点后
	}
	return newHead;
}
ListNode *ReverseList2(ListNode *pHead)//依次改变指针方向(改变链表结构)
{
	ListNode *pre=NULL;
	ListNode *p=NULL;
	while(pHead!=NULL){
		p=pHead->next;	//保存剩余链表
		pHead->next=pre;//断开剩余链表头结点pHead,指向pre
		pre=pHead;	//pre更新
		pHead=p;	//head更新
	}
	return pre;
}

int main()//主函数
{
	int n;
	cin>>n;	//输入元素个数					
	ListNode* head=NULL;
	ListNode* p=NULL;
	ListNode* q=NULL;
	for(int i=0;i<n;i++)//分配内存,依次输入元素
	{
		q=new ListNode;	
		cin>>q->value;
		if(head==NULL)
		{
			head=q;
			p=head;
		}
		else
		{
			p->next=q;
			p=p->next;
		}
	}
	if(head==NULL)
		return 0;
	p->next=NULL;
	//验证
	cout<<"递归逆序打印: "<<endl;
	ReversePrint(head);	
	cout<<endl<<"头插法反转链表: "<<endl;
	ListNode* reverseHead;
	reverseHead = ReverseList1(head);
	p=reverseHead;
	while(p!=NULL)
	{
		cout<<p->value<<" ";
		p=p->next;
	}
	cout<<endl<<"改变指针方向反转链表(将链表再次反转): "<<endl;
	p = ReverseList2(reverseHead);	//改变指针方向反转链表
	while(p!=NULL)
	{
		cout<<p->value<<" ";
		q=p;
		p=p->next;
		delete q;//释放内存
	}
	cout<<endl;
	return 0;
}

方法4:利用一个栈

void printListFromTailToHead(ListNode *pHead)
{
	stack<ListNode*> nodes;
	ListNode *p=pHead;
	while(p!=NULL)
	{
		nodes.push(p);//入栈
		p=p->next;
	}
	while(!nodes.empty())
	{
		p=nodes.top();//赋值
		cout<<p->val<<endl;
		nodes.pop();//删除栈顶元素
	}
}


版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/kc58236582/article/details/77503376

智能推荐

FAT32文件_fat32返回值-程序员宅基地

文章浏览阅读1.1k次。/*---------------------------------------------- * 模 块 名:文件系统 * 功能描述:读写基于FAT32格式的数据 * 调试平台:UMP3 * * 当前版本:1.0 * 作 者:xx * 完成日期:2010-6-28 * 存在BUG:未知 * 调试结果:完成调试 * * 说 明:本文件系统_fat32返回值

Python初学者笔记(3):输出列表中的奇数/奇数项,字符串中的偶数项,字符串大小写转换...-程序员宅基地

文章浏览阅读4.5k次,点赞2次,收藏12次。【1】a=[8,13,11,6,26,19,24]1)请输出列表a中的奇数项2)请输出列表a中的奇数解:1)1 a=[8,13,11,6,26,19,24]2 print a[::2]Result:>>>[8, 11, 26, 24]2)1 a = [8,13,11,6,26,19,24]2 b = []3 for it..._用for语句筛选出自然数序列中的奇数与偶数,分别存入奇数列表ls1 与 偶数列表ls2,分两行打印输出

Python安装包下载、环境配置与工具包安装教程(详细版)_pystdf安装包-程序员宅基地

文章浏览阅读7k次,点赞11次,收藏62次。一、安装包下载网盘:链接:https://pan.baidu.com/s/1FrFj8Flcwr_ZJH91OxoF5A 提取码:2442二、环境配置1、下载完解压后双击 python-3.8.0a4-amd64.exe,注意:一定勾选Add Python 3.8 to PATH, 会自动配置环境变量 2、在cmd中输入python 验证是否安装成功三、工具包下载1、安装pip,首先进入cmd命令是:pip install pip查看是否安装成功命令: == pip show pi_pystdf安装包

从.NET平台调用Win32 API_.net 调用win32的程序需要安装到本地才能使用吗-程序员宅基地

文章浏览阅读503次。作者:刘铁猛日期:2005-12-20关键字:C# .NET Win32 API版权声明:本文章受知识产权法保护,如果阁下想转载,在转载的时候烦劳阁下连同在下的姓名一起转载,并向[email protected]发一个Mail,我很想知道我的文章都去哪里了.谢谢.小序 Win32 API可以直接控制Microsoft Windows的核心,因为API(Applicati_.net 调用win32的程序需要安装到本地才能使用吗

ssh框架发布json数据提供客户端开发_ssh提供向其他系统发送数据的接口-程序员宅基地

文章浏览阅读1.6k次,点赞3次,收藏2次。作为一个客户端开发人员,每次让服务端人员写数据接口的的时候,感觉就像是在求他们一样,与其求别人,还不如自己会搞,android与服务端通行,最常见的就是json了,以前用webservice,感觉还可以,总之,多一种通行方式多一套方法,多一个机会吧!大三了,感觉心里惶惶的,但是还是得学习呀。 先看看效果吧 注意:*浏览器的参数名称必须要和action里面的接收的名称一样,要不然接收不到参数*_ssh提供向其他系统发送数据的接口

Python---生成器_python转换器-程序员宅基地

文章浏览阅读254次。生成器是什么?用来干什么:生成器是生成一个算法,生成一组有规律的数。用途见后期更新生成器的两种生成方式:(1)修改列表生成式生成简单的生成器(2)在实现一个算法推算的函数中加入yield语句生成复杂的生成器。那么什么是列表生成式呢:a=[]for i in range(20): a.append(i*i)print(a)这两种形式可以生成一个list,..._python转换器

随便推点

准备全面进行了-程序员宅基地

文章浏览阅读209次。根据这两个月的试用期,带我的那哥们告诉我应该转正没问题。另外,转了UE4后,发现找的猎头和HR很多,看来,也要好好重视了。不能只把UE4当UI使用了。当然,由于刚转,薪水也就都是20k起步,不如现在25K,这几年没有任何跳槽的必要。一,UE4学习上:我认为,UE4学习分为4个层次,第一层次:SLATE+业务。slate,这个不是问题。主要是业务上,多看看视频教程,也就OK。工作要求也就是停留在第一层次上。但是不能两个月的经验当三年用,那样肯定会被年轻人替代,淘汰是必然结果。第二层次:文档_准备全面

最大流-FoldFulkerson算法_fold-fulkerson算法-程序员宅基地

文章浏览阅读2.9k次。问题来源:hdu-1532问题描述:约翰是个农民,每次下雨的时候他的庄家总是会被淹没,这就意味着当庄家被水淹后需要很长时间才能重新生长出来,因此,约翰已经建立了一系列排水管道为了使他的庄家尽可能被淹没的最少,也就是说管道的排水量必须很大.作为一名工程师,约翰可以计算出管道网能排水的最大能力.Input:输入包含多组用例,每组用例第一行是两个数N,M,N表示一共有N个管道,M表示一共有M个点_fold-fulkerson算法

理解iOS Event Handling-程序员宅基地

文章浏览阅读74次。写在前面最近的一个iOS App项目中遇到了这么问题:通过App访问服务器的大多数资源不需要登录,但是访问某些资源是需要用户提供验证的,一般来说,通常App的做法(譬如美团App)将这些资源放在“我的”模块,在未登录情况下,当点击“我的”某个模块时,以modally给出一个界面用于登录,我不晓得美团是怎么实现的;但在我看来,比较优雅的方式是在网络底层实现“modally呈现登录界面”..._ios event handling

MVC浅析(实际上应该是MVP,有时间再更新该博客)-程序员宅基地

文章浏览阅读344次。以Android中登录过程为例简单说明,其他应用场景同理。 定义接口: Model层:IModelLogin.javapublic interface IModelLogin { /** * 开始登录请求 * @param username * @param password */ abstract void iStartLogin(Stri

Percona MySQL Server 部署指南-程序员宅基地

文章浏览阅读784次。公众号关注「奇妙的 Linux 世界」设为「星标」,每天带你玩转 Linux !一、版本信息目前采用 MySQL fork 版本 Percona Server 5.7.28,监控方面选...

linux下文件恢复工具extundelete_extundelete /dev/sda2-程序员宅基地

文章浏览阅读861次。linux下文件恢复工具extundelete一. 条件假设目前系统中有个sda2分区,里面有个文件夹directory1,文件夹里含有文件test_pass1和另一个子文件夹directory2,文件夹directory2里含有一个文件test_pass2,现在删除directory1这个文件夹,并想要恢复里面的文件二.使用方法① 安装extundeleteyum install e2fsprog_extundelete /dev/sda2