首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
输入一个链表的头结点,从尾到头反过来输出每个结点的值。链表结点定义如下: struct ListNode { int m_nKey; ListNode* m_pNext; };
输入一个链表的头结点,从尾到头反过来输出每个结点的值。链表结点定义如下: struct ListNode { int m_nKey; ListNode* m_pNext; };
admin
2019-03-29
127
问题
输入一个链表的头结点,从尾到头反过来输出每个结点的值。链表结点定义如下:
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
程序员面试
相关试题推荐
TheUnitedStatesInterstateHighwaySystemisaninfrastructurefeatofunprecedentedproportions.Notonlydoesitjoinallfi
Weakdollarorno,$46,000—thepriceforasingleyearofundergraduateinstructionamidtheredbrickofHarvardYard—is【C1】__
Weakdollarorno,$46,000—thepriceforasingleyearofundergraduateinstructionamidtheredbrickofHarvardYard—is【C1】__
Writeanessaybasedonthefollowingoutline.Youshouldwriteabout150wordsontheANSWERSHEET.1.教师用课外时间给学生补课赚钱的现象
输入一个英文句子,翻转句子中单词的顺序,但单词内字符的顺序不变。句子中单词以空格符隔开。为简单起见,标点符号和普通字母一样处理。例如输入“Iamastudent.”,则输出“student.aamI”。
输入一棵二元查找树,将该二元查找树转换成一个排序的双向链表。要求不能创建任何新的结点,只调整指针的指向。 比如将二元查找树转换成双向链表4=6=8=10=12=14=16。
大概描述一下ASP。NET页面的生命周期
Office2000Office2000中文版中文版用()实现A.插入符号B.并排字符C.组合字符D.首字下沉
路由器的主要作用是()。
随机试题
患者,女性,45岁,偶然发现左乳房肿块,直径约2cm,质较软、无压痛,与皮肤有少许粘连。左侧腋下可扪及1cm大小肿大的淋巴结。该患者的术后护理措施中不正确的是()。
汉代的以下诉讼制度中,()在一定程度上有利于实现司法公正。
下面关于城市社区管理说法正确的是()。
详细可行性研究阶段的投资估算,其误差率应控制在()以内。
案情简介:京海造纸厂因超标排污影响了周围环境,居民李某等多次找环保局要求解决。1996年2月8日,环保局对造纸厂作出罚款3000元、责令停止排污的处罚决定。此后3个月内,造纸厂既不履行处罚决定,也未向法院起诉。起诉期过后,环保局向人民法院申请强制
我国宏观调控的主要目标是()。
Thegreatestrecentsocialchangeshavebeeninthelivesofwomen.Duringthetwentiethcenturytherehasbeenaremarkablesho
•Readthefaxbelowaboutpeopleexpress.•ChoosethebestwordtofilleachgapfromA,B,CorDontheoppositepage.•For
Lunarsight-seeingtripsandorbitingspacehotelsarewithinreach,moonwalkingastronautEdwin"Buzz"Aldrinsaidlastweek,b
A、Therighthand.B、Thelefthand.C、Bothhands.D、Itdepends.B原文提到,婴儿16周大时,主要使用左手进行触摸,因此B正确。
最新回复
(
0
)