首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
输入一个链表的头结点,从尾到头反过来输出每个结点的值。链表结点定义如下: struct ListNode { int m_nKey; ListNode* m_pNext; };
输入一个链表的头结点,从尾到头反过来输出每个结点的值。链表结点定义如下: struct ListNode { int m_nKey; ListNode* m_pNext; };
admin
2019-03-29
153
问题
输入一个链表的头结点,从尾到头反过来输出每个结点的值。链表结点定义如下:
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
Publicationbiasinacademicjournalsisnothingnew.Afindingofnocorrelationbetweensportingeventsandeitherviolentcri
Publicationbiasinacademicjournalsisnothingnew.Afindingofnocorrelationbetweensportingeventsandeitherviolentcri
输入一个整数和一棵二元树。从树的根结点开始往下访问一直到叶结点所经过的所有结点形成一条路径。打印出和与输入整数相等的所有路径。例如输入整数22和如下二元树10
重载与覆盖的区别
.asp.net如何实现MVC模式,举例说明!
求最大连续递增数字串(如“ads3sl456789DF3456ld345AA”中的“456789”)
输入一个字符串,打印出该字符串中字符的所有排列。例如输入字符串abc,则输出由字符a、b、c所能排列出来的所有字符串abc、acb、bac、bca、cab和cba。
存储过程和函数的区别
计算机能直接识别和执行的语言是()A.机器语言B.高级语言C.数据库语言D.汇编程序
随机试题
影响显示器显示清晰程度的一个重要指标是()。
男,10岁,小学生,起病急,畏寒,高热,头痛呕吐已8小时,目前呼之不应。检查:神志不清,面色苍白,四肢厥冷,体温40℃,全身见有广泛斑点、淤斑,有的呈片状,脉细速,血压5.2/0kPa,颈软,脑膜刺激征阴性,血象38×109/L,N0.92,L0.0
患者男,59岁,工人。1年前无明显诱因出现双腕、双手关节和双膝、踝、足、跖趾关节肿痛,伴晨僵;时间约12分钟,疼痛以夜间明显,影响行动。实验室检查:血沉55mm/L,RF(+)。关节X线检查:双手骨质疏松,腕部关节间隙变窄。使用青霉胺治疗,护士应观察哪些
下列关于食品安全管理的法律规定,说法正确的是:
某企业拟采购一批原材料,价值10000元,供应商规定的付款条件如下:(1)立即付款,价格9630元;(2)第20天付款,价格9750元;(3)第40天付款,价格9870元;(4)第60天付款,价格10000元。要求:假设银行短期贷款的利率为23
以下对采购与付款业务流程中付款环节的控制活动以及与相关认定的对应关系的陈述中,不恰当的是()。
在音乐作品中,由原调经过某种中间环节进新调,并在新调上有完全的终止,称之为_________。如果在新调上没有完全的终止,则称之为_________。
2009年H省年末常住人口达到7034.4万人,出生人口90.7万人,出生率为12.93‰;死亡人口45.1万人,死亡率为6.43‰;净增人口45.6万人。2009年城镇居民人均可支配收入达14718.3元。其中,工资性收入9830.6元,增长1
下列关于正当防卫和紧急避险的表述中,正确的是()。
Researchhasshownthatcollegestudentscanlearnasmuch,ormore,frompeersastheydofrominstructorsandtextbooks.When
最新回复
(
0
)