首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
输入一个链表的头结点,从尾到头反过来输出每个结点的值。链表结点定义如下: struct ListNode { int m_nKey; ListNode* m_pNext; };
输入一个链表的头结点,从尾到头反过来输出每个结点的值。链表结点定义如下: struct ListNode { int m_nKey; ListNode* m_pNext; };
admin
2019-03-29
44
问题
输入一个链表的头结点,从尾到头反过来输出每个结点的值。链表结点定义如下:
struct ListNode
{
int m_nKey;
ListNode* m_pNext;
};
选项
答案
/////////////////////////////////////////////////////////////////////// // Print a list from end to beginning // Input: pListHead - the head of list /////////////////////////////////////////////////////////////////////// void PrintListReversely(ListNode* pListHead) { if(pListHead != NULL) { // Print the next node first if (pListHead->m_pNext != NULL) { PrintListReversely(pListHead->m_pNext); } // Print this node printf("%d", pListHead->m_nKey); } }
解析
这是一道很有意思的面试题。该题以及它的变体经常出现在各大公司的面试、笔试题中。
看到这道题后,第一反应是从头到尾输出比较简单。于是很自然地想到把链表中链接结点的指针反转过来,改变链表的方向。然后就可以从头到尾输出了。反转链表的算法详见本人面试题精选系列的第19题,在此不再细述。但该方法需要额外的操作,应该还有更好的方法。
接下来的想法是从头到尾遍历链表,每经过一个结点的时候,把该结点放到一个栈中。当遍历完整个链表后,再从栈顶开始输出结点的值,此时输出的结点的顺序已经反转过来了。该方法需要维护一个额外的栈,实现起来比较麻烦。
既然想到了栈来实现这个函数,而递归本质上就是一个栈结构。于是很自然的又想到了用递归来实现。要实现反过来输出链表,我们每访问到一个结点的时候,先递归输出它后面的结点,再输出该结点自身,这样链表的输出结果就反过来了。
转载请注明原文地址:https://kaotiyun.com/show/rRmZ777K
0
程序员面试
相关试题推荐
Weakdollarorno,$46,000—thepriceforasingleyearofundergraduateinstructionamidtheredbrickofHarvardYard—is【C1】__
输入一个整形数组,数组里有正数也有负数。数组中连续的一个或多个整数组成一个子数组,每个子数组都有一个和。求所有子数组的和的最大值。要求时间复杂度为O(n)。例如输入的数组为1,-2,3,10,-4,7,2,-5,和最大的子数组为3,10,
输入n个整数,输出其中最小的k个。例如输入1,2,3,4,5,6,7和8这8个数字,则最小的4个数字为1,2,3和4。
大概描述一下ASP。NET页面的生命周期
定义字符串的左旋转操作:把字符串前面的若干个字符移动到字符串的尾部。如把字符串abcdef左旋转2位得到字符串cdefab。请实现字符串左旋转的函数。要求时间对长度为n的字符串操作的复杂度为O(n),辅助内存为O(1)。
在Excel中,函数ABS(ROUND(-1.478,2))的计算结果是()。A.-1.478B.1.48C.-1.48D.1.5
【程序说明】使用如下表的数据:SQL语句SELECT部门表.部门号,部门名称,商品号,商品名称,单价;FROM部门表,商品表;WHERE部门表.部门号=商品表.部门号;ORDERBY部门表.部门号DESC,单价
企业战略数据模型可分为两种类型:(35)描述日常事务处理中的数据及其关系;(36)描述企业管理决策者所需信息及其关系。35
对计算机评价的主要性能指标有时钟频率、①、运算精度和内存容量等。对数据库管理系统评价的主要性能指标有②、数据库所允许的索引数量和最大并发事务处理能力等。①处应填入?
随机试题
下列哪种刊物的创刊是日本无产阶级文学诞生的标志【】
(2011年4月)(2005年4月)1878年法国最高法院对_____的判决是关于法律规避问题的一个著名判决。
抽样的理论基础是()
礞石滚痰丸适用于中风之
苯妥英钠是哪种癫痫发作的首选药物
挖眼接管三通,支线管径小于主管径的1/2时,应( )。
非公开发行股票的发行对象不超过15名。()
IfyoucometoAustralia,leaveyournaughtyhabitsatthedoor.Ifyoulivehere,getbackinyourbox.TheAustraliangover
文件系统中,若将逻辑上连续的文件信息分散存放在若干不连续的磁盘块中,并将所有磁盘块的地址集中存放在一张表中,这种结构称为()。
“福星一号”发射成功,并完成与“银星一号”对接等任务,全国人民为之振奋和鼓舞,作为航天城中国航天博览馆讲解员的小苏,受领了制作“福星一号飞船简介”的演示幻灯片的任务。请你根据考生文件夹下的“福星一号素材.docx”素材文件,帮助小苏完成制作任务,具体要求如
最新回复
(
0
)