首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
输入一个链表的头结点,反转该链表,并返回反转后链表的头结点。链表结点定义如下: { int m_nKey; ListNode* m_pNext; };
输入一个链表的头结点,反转该链表,并返回反转后链表的头结点。链表结点定义如下: { int m_nKey; ListNode* m_pNext; };
admin
2019-03-29
89
问题
输入一个链表的头结点,反转该链表,并返回反转后链表的头结点。链表结点定义如下:
{
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://jikaoti.com/ti/Fag7FFFM
0
程序员面试
相关试题推荐
[A]TherelativelylowtuitionfeesinAsiaarealsoamaindrawforprospectivestudents.Lastyear,onlinehighereducationre
YouhavereceivedaletterfromSophia.Sheexpressedheradmirationformicro-bloggingandwonderedwhetheritcanreplacebook
输入一棵二元查找树,将该二元查找树转换成一个排序的双向链表。要求不能创建任何新的结点,只调整指针的指向。 比如将二元查找树转换成双向链表4=6=8=10=12=14=16。
不开辟新空间完成字符串的逆序
一个整型数组里除了两个数字之外,其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n),空间复杂度是O(1)。
数据库的优化设计?
Word的样式是一组巳命名的字符和()格式的组合。
下面哪些属于中国域名()A.MicrosoftB.eeec.comC.ibm……ilD.bta.cn
请根据设计模板创建演示文稿,命名为“总结”,保存在D盘根目录下。
在使用SELECT-SQL语句进行查询操作时,可以进行集合的并运算,即将多个基本的SELECT-SQL语句运行结果进行合并。这时,需要使用关键词(或称为运算符)________将多个基本的SELECT-SQL语句进行组合。
随机试题
黄牛,3岁,出现流涎,嘴角挂有大量泡沫,有食欲但采食后咀嚼缓慢、吐草。诊断本病需进一步进行
参苓白术散组成中有
妊娠期妇女不宜选用的抗菌药物类别是()。
甲和乙共有房屋三间,出租给丙开办商店。现丁要向戊借款5万元,在丁的要求下,征得乙的同意后,甲将其在上述三间房屋中的共有份额抵押给戊,并在通知丙后,到房屋管理局作了登记。对其中的法律关系,下列表述正确的是()。
设备监理单位的资格等级分为甲、乙两级,各级别设备监理单位应符合设备监理单位定义中的基本要求外,还应具备()个条件。
根据《人民币银行结算账户管理办法》的规定,存款人虽宣告破产,但尚未清偿其开户银行债务的,不得申请撤销该账户。()
全球金属期货的发源地和目前最大的金属期货交易中心是()。
某工程的年度预算为1260万元,到四月份结束时,已花了458万元。如果在后八个月每月都用了前四个月的均数,问这个年度该工程要超支多少钱?
从高考成绩来看。北京考生的分数并没有“一枝独秀”,但媒体报道,今年清华共录取北京考生295人,在京扩招比例达45.3%;北大扩招33.6%,录取294人。然而清华北大在其他省市录取的考生,少则几人,多则几十、百把人,实在是天壤之别。可见我国高等教育的不公平
Concerningmoneyoranythingelse,conflictsbetweenhusbandandwifeusuallyreflectapowerstruggle.Conflictsbetweenparent
最新回复
(
0
)