首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
输入一个链表的头结点,反转该链表,并返回反转后链表的头结点。链表结点定义如下: { int m_nKey; ListNode* m_pNext; };
输入一个链表的头结点,反转该链表,并返回反转后链表的头结点。链表结点定义如下: { int m_nKey; ListNode* m_pNext; };
admin
2019-03-29
147
问题
输入一个链表的头结点,反转该链表,并返回反转后链表的头结点。链表结点定义如下:
{
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
程序员面试
相关试题推荐
编码实现字符串转整型的函数(实现函数atoi的功能),据说是神州数码笔试题。如将字符串”+123”-->123,”-0123”-->-123,“123CS45”-->123,“123.45CS”-->123,“CS123.45”-->0
歌德巴赫猜想。任何一个偶数都可以分解为两个素数之和。
将上题的规则应用到已下载的邮件。
从当前界面上的菜单或“网络任务”开始创建拨号连接,通过Modem连接到In-ternet,拨号时先拨0,再拨16300,用户名和密码均为16300,将创建的连接的名称命名为:linkl,然后在桌面上创建一个到此连接的快捷方式。除此之外,其余选项均使用默认设
利用快捷方式向导,在桌面上为文件夹“C:\office”中的应用程序“EXCEL.EXE”创建名为“EXCEL”的快捷方式。
利用“开始”菜单“所有程序”启动“计算器”应用程序。
在Word97的编辑状态,执行“文件”菜单中的“保存”命令后()。A.将所有打开的文档存盘B.只能将当前文档存储在原文件夹的文件内C.可以将当前文档存储在已有的任意文件夹内D.可以先建立一个新文件夹,再将文档存储在该文件夹内
对于PPoint来说,以下说法正确的是()。A.启动PPoint后直到关闭的过程中,只能建立或编辑一个演示文稿文件B.启动PPoint后直到关闭的过程中,可以建立或编辑多个演示文稿文件C.启动PPoint后,不能编辑多个演示文稿文件D.启动
设置围绕表格的边框宽度的HTML代码是______。A.tablesize=#B.tableborder=#C.tablebordersize=#D.tableborder=#
在实际应用中,用户通常依靠评价程序来测试系统的性能。以下评价程序中,(16)的评测准确程度最低。事务处理性能委员会(TransactionProcessingPerformanceCouncil,TPC)是制定商务应用基准程序(Benchmark)标
随机试题
过敏性紫癜性肾炎可表现为()Ns可表现为()
怎样绘制电缆施工图?
张某和李某合谋,由与赵某熟识的张某将赵某骗到外地游玩,然后李某给赵某的家人打电话声称赵某已被绑架,并要求赵某家人拿钱赎人,否则就要“撕票”。赵某家人依照李某的要求支付了赎金。张某和李某的行为不构成哪些罪?()
(2015年真题)根据我国选举法,设区的市的人大代表提出辞职,正确的做法是()。
如果监理工程师将不合格的建筑材料、建筑构配件和设备按照合格签字,造成工程质量事故,由此引发安全事故的,则()。
建设工程职业健康安全事故按事故后果严重程度分类有()。
下列各项中,属于行为税类的有()。
()系统研究了作为“社会人”的员工及其社会需要的满足问题,最终创立了人际关系学说。
中央八项规定之所以取得成效,关键是中央政治局以身作则、___________。各级领导干部要充分认识自己在作风建设中的关键地位和重要作用,以及对党和国家前途命运的重大责任,以___________、如临深渊的小心和谨慎,对待自己的一言一行,一举一动。要带头
马克思说:“在选择职业时,我们应当遵循的指针是人类的幸福和我们自身的实现。不应该认为选这两种利益是敌对的、互相冲突的。”这里,马克思说为人类谋幸福是人生的()
最新回复
(
0
)