首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
输入一个链表的头结点,反转该链表,并返回反转后链表的头结点。链表结点定义如下: { int m_nKey; ListNode* m_pNext; };
输入一个链表的头结点,反转该链表,并返回反转后链表的头结点。链表结点定义如下: { int m_nKey; ListNode* m_pNext; };
admin
2019-03-29
130
问题
输入一个链表的头结点,反转该链表,并返回反转后链表的头结点。链表结点定义如下:
{
int m_nKey;
ListNode* m_pNext;
};
选项
答案
/////////////////////////////////////////////////////////////////////// // Reverse a list iteratively // Input: pHead - the head of the original list // Output: the head of the reversed head /////////////////////////////////////////////////////////////////////// ListNode* ReverseIteratively(ListNode* pHead) { ListNode* pReversedHead = NULL; ListNode* pNode = pHead; ListNode* pPrev = NULL; while(pNode != NULL) { // get the next node, and save it at pNext ListNode* pNext = pNode->m_pNext; // if the next node is null, the currect is the end of original // list, and it’s the head of the reversed list if(pNext == NULL) pReversedHead = pNode; // reverse the linkage between nodes pNode->m_pNext = pPrev; // move forward on the the list pPrev = pNode; pNode = pNext; } return pReversedHead; }
解析
这是一道广为流传的微软面试题。由于这道题能够很好的反应出程序员思维是否严密,在微软之后已经有很多公司在面试时采用了这道题。
为了正确地反转一个链表,需要调整指针的指向。与指针操作相关代码总是容易出错的,因此最好在动手写程序之前作全面的分析。在面试的时候不急于动手而是一开始做仔细的分析和设计,将会给面试官留下很好的印象,因为在实际的软件开发中,设计的时间总是比写代码的时间长。与其很快地写出一段漏洞百出的代码,远不如用较多的时间写出一段健壮的代码。
为了将调整指针这个复杂的过程分析清楚,我们可以借助图形来直观地分析。假设下图中l、m和n是三个相邻的结点:
a?b?…?l mànà…
假设经过若干操作,我们已经把结点l之前的指针调整完毕,这些结点的m_pNext指针都指向前面一个结点。现在我们遍历到结点m。当然,我们需要把调整结点的m_pNext指针让它指向结点l。但注意一旦调整了指针的指向,链表就断开了,如下图所示:
a?b?…l?m nà…
因为已经没有指针指向结点n,我们没有办法再遍历到结点n了。因此为了避免链表断开,我们需要在调整m的m_pNext之前要把n保存下来。
接下来我们试着找到反转后链表的头结点。不难分析出反转后链表的头结点是原始链表的尾位结点。什么结点是尾结点?就是m_pNext为空指针的结点。
转载请注明原文地址:https://kaotiyun.com/show/7xmZ777K
0
程序员面试
相关试题推荐
AskingforMoreTimetoFinishaTask请求给予更多时间来完成任务Writealetterofabout100wordsbasedonthefollowingsituation:Youfail
Signslike"Pleaseratemefivestars"pointtoagrowingproblemwithbusinessesintheon-demandeconomyofapp-basedservices
.什么叫应用程序域?什么是受管制的代码?什么是强类型系统?什么是装箱和拆箱?什么是重载?CTS、CLS和CLR分别作何解释?
一个整型数组里除了两个数字之外,其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n),空间复杂度是O(1)。
将“回收站”的最大空间设置为每个驱动器的10%。
在WindowsXP的桌面上打开"回收站"的窗口。
Excel2000中,列标()A.可以用各种符号表示B.用数字表示C.用字母表示D.可以用中文文字表示
对于PPoint中的视图模式,以下说法错误的是()。A.幻灯片浏览视图下不能设置放映方式B.幻灯片视图注重于对幻灯片的文本和对象进行详细操作C.每种视图模式在演示文稿的制作和显示中有不同的作用D.大纲视图便于查看和编排演示文稿的大纲
对数据排序时,下列操作错误的是()A.选清单中任意一个单元格B.选清单做排序操作C.选清单中任意一行排序D.选工作表中任意一个单元格排序
根据防火墙的功能来理解,我们认为防火墙不可能()。
随机试题
羊水过多的常见胎儿异常为神经管畸形。而羊水随少者则为泌尿道畸形。()
患者,女性,26岁,因手背部皮肤碾挫伤,肌腱暴露,给予行腹部皮瓣覆盖创面。术后体位
根据《中华人民共和国药品管理法实施条例》,中药饮片的标签不须注明的内容是
一位心理医生计划在给患者进行心理治疗时录像,一方面是为了积累科研资料,另一方面是为了教学使用。但是,如果让患者知道此事势必将影响其心理状态而不利于治疗,也不利于科研的准确性和教学录像的质量。 在这种情况下,这位心理医生如何选择最佳策略?(
[2010年,第21题]设事件A与B相互独立,且等于()。
对于一般的监理业务流程,在开始实施监理的具体工作时,( )工作应已经完成。
工程施工质量事故的处理工作包括:①事故调查;②事故原因分析;③事故处理;④事故处理的鉴定验收;⑤制订事故处理方案。正确的处理程序是()。
一位新入园的儿童问老师:“妈妈什么时候来接我?”老师最好的回答是()。
WhatwillthemandoonSaturday?
Whotobelieve?NokiaorEricsson?IBMorSunMicrosystems?MicrosoftorSiebel?Rarelyhavethefortunesoftechnologycompanie
最新回复
(
0
)