首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
输入一个链表的头结点,从尾到头反过来输出每个结点的值。链表结点定义如下: struct ListNode { int m_nKey; ListNode* m_pNext; };
输入一个链表的头结点,从尾到头反过来输出每个结点的值。链表结点定义如下: struct ListNode { int m_nKey; ListNode* m_pNext; };
admin
2019-03-29
132
问题
输入一个链表的头结点,从尾到头反过来输出每个结点的值。链表结点定义如下:
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
程序员面试
相关试题推荐
[A]Forcrowdfundingtowork,theprojectneedstocapturethepublicimagination.Andnotallacademicsarecomfortablewithse
Weakdollarorno,$46,000—thepriceforasingleyearofundergraduateinstructionamidtheredbrickofHarvardYard—is【C1】__
编码实现字符串转整型的函数(实现函数atoi的功能),据说是神州数码笔试题。如将字符串”+123”-->123,”-0123”-->-123,“123CS45”-->123,“123.45CS”-->123,“CS123.45”-->0
活动目录的作用
如何部署一个ASP.net页面。
输入一个单向链表,输出该链表中倒数第k个结点。链表的倒数第0个结点为链表的尾指针。链表结点定义如下:structListNode{intm_nKey;ListNode*m_pNext;};
在当前界面【管理工具】窗口中,设置Windows密码策略,将密码长度最小值设置为8个字符。
对于PPoint中的视图模式,以下说法错误的是()。A.幻灯片浏览视图下不能设置放映方式B.幻灯片视图注重于对幻灯片的文本和对象进行详细操作C.每种视图模式在演示文稿的制作和显示中有不同的作用D.大纲视图便于查看和编排演示文稿的大纲
在Excel中,公式SUM(C2:C6)的作用是()。A.求C2到C6这五个单元格数据之和B.求C2和C6这两个单元格数据之和C.求C2和C6两单元格的比值D.以上说法都不对
路由器的主要作用是()。
随机试题
职业纪律是茶艺从业人员在茶艺()活动中必须遵守的行为准则。
Maryseemsto______agoodmemoryforshecanlearnsuchalongpassagebyheart.
男性,19岁。尿呈洗肉水样1周,每日尿量约1000mL。临床拟诊为IgA肾病。最需要鉴别的继发性IgA沉积的肾小球疾病是
禽流感病毒H亚型分型的物质基础是()
下列选项中,囊肿壁中含皮肤附属器的是
企业从事公益活动的影响包括()。
套期保值与期现套利的区别包括()不同。Ⅰ.价位观念Ⅱ.在现货市场上所处的地位Ⅲ.交易目的Ⅳ.操作方式
根据《企业会计准则》企业利润分为()。
2006年至2011年全年我国农村居民人均纯收入分别为3587元、4140元、4761元、5153元、5919元、6977元;城镇居民人均可支配收入分别为11759元、13786元、15781元、17175元、19109元、21810元。2006年至201
A、Bydoingbusiness.B、Bybuyingandsellingland.C、Bycheating.D、Bymakingwhiskey.AHowdidJohnsonbecomerichaccordingto
最新回复
(
0
)