首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
输入一个链表的头结点,反转该链表,并返回反转后链表的头结点。链表结点定义如下: { int m_nKey; ListNode* m_pNext; };
输入一个链表的头结点,反转该链表,并返回反转后链表的头结点。链表结点定义如下: { int m_nKey; ListNode* m_pNext; };
admin
2019-03-29
107
问题
输入一个链表的头结点,反转该链表,并返回反转后链表的头结点。链表结点定义如下:
{
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
程序员面试
相关试题推荐
Thecommitteehasanticipatedtheproblemsthat______intheroadconstructionproject.
输入一个表示整数的字符串,把该字符串转换成整数并输出。例如输入字符串"345",则输出整数345。
设置网络连接,使之在连接后在通知区域显示连接状态,用【自动获取IP地址】的方式获得IP,并查看该连接的IP地址和DNS服务器地址。
利用"开始"菜单的"运行"选项,启动"计算器"应用程序,计算器应用程序的标识为:c:\windows\system32\calc.exe(在"打开"中直接填写标识名)。
利用快捷方式向导,在桌面上为文件夹“C:\office”中的应用程序“EXCEL.EXE”创建名为“EXCEL”的快捷方式。
在Excel中,函数ABS(ROUND(-1.478,2))的计算结果是()。A.-1.478B.1.48C.-1.48D.1.5
路由器的主要作用是()。
创建一个接口的正确路径是什么?A、CONTROLLER>Interfaces>NewB、CONTROLLER>Inventory>NewInterfaceC、INTERFACES>NewD、CONTROLLER>Ports>New
软件需求可以分为功能需求、性能需求、外部接口需求、设计约束和质量属性等几类。以下选项中,()均属于功能需求。①对特定范围内修改所需的时间不超过3s②按照订单及原材料情况自动安排生产排序③系统能够同时支持1000个独立站点的并发访问
在网络工程规划与设计过程中,选择防火墙之前应该考虑的因素有哪些?请用300字以内的文字简要回答。请为图4-13拓扑结构中PIX525防火墙各接口命名,并指定相应的安全级别和IP地址的配置语句。
随机试题
在Word2010中,要将相邻两个页面的方向分别设置成横向和纵向,则在设置页面方向之应进行的操作是________。
复原重置成本与更新重置成本的相同点在于,计算时所采用的________是相同的()
血液保存液ACD加入下列哪种物质可变为CPD
根据合同法律制度的规定,下列各项中,属于无效合同的有()。
甲公司因欲建造一栋办公楼,向乙银行借款3000万元,双方同时约定,甲公司以其取得的用于建造该办公楼的建设用地使用权为乙银行设立抵押权,担保该3000万元借款债务。双方办理了建设用地使用权的抵押登记。此后,甲公司与丙建筑公司签订建设工程施工合同,约定由丙公司
(2010年)若希望实现三相异步电动机的向上向下平滑调速,则应采用()。
《建筑法》及相关建设法规规定,施工单位允许他人以自己的名义承揽工程,按规定可进行下列除()以外的处罚。
被保险人或者投保人可以变更受益人并书面通知保险人。保险人收到变更受益人的书面通知后,应当在保险单上批注。投保人变更受益人时须经被保险人同意。( )
Heworkstenhoursaday,makesmorethanUS$98,000ayear,doesn’tbothertotakeholidays,dressesashepleases,he’sne
在考生文件夹下,打开文档Word1.docx,按照要求完成下列操作并以该文件名Word1.docx保存文档。将标题段文字(“搜狐荣登Netvaluc五月测评榜首”)设置为小三号宋体、红色、加下划线、居中并添加蓝色(标准色)底纹,文本效果为:渐变填充一黑
最新回复
(
0
)