首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
给定链表的头指针和一个结点指针,在O(1)时间删除该结点。链表结点的定义如下: struct ListNode { int m_nKey; ListNode* m_pNext; }; 函数的声明如下: void DeleteNode(L
给定链表的头指针和一个结点指针,在O(1)时间删除该结点。链表结点的定义如下: struct ListNode { int m_nKey; ListNode* m_pNext; }; 函数的声明如下: void DeleteNode(L
admin
2019-03-29
131
问题
给定链表的头指针和一个结点指针,在O(1)时间删除该结点。链表结点的定义如下:
struct ListNode
{
int m_nKey;
ListNode* m_pNext;
};
函数的声明如下:
void DeleteNode(ListNode* pListHead, ListNode* pToBeDeleted);
选项
答案
/////////////////////////////////////////////////////////////////////// // Delete a node in a list // Input: pListHead - the head of list // pToBeDeleted - the node to be deleted /////////////////////////////////////////////////////////////////////// void DeleteNode(ListNode* pListHead, ListNode* pToBeDeleted) { if(!pListHead || !pToBeDeleted) return; // if pToBeDeleted is not the last node in the list if(pToBeDeleted->m_pNext != NULL) { // copy data from the node next to pToBeDeleted ListNode* pNext = pToBeDeleted->m_pNext; pToBeDeleted->m_nKey = pNext->m_nKey; pToBeDeleted->m_pNext = pNext->m_pNext; // delete the node next to the pToBeDeleted delete pNext; pNext = NULL; } // if pToBeDeleted is the last node in the list else { // get the node prior to pToBeDeleted ListNode* pNode = pListHead; while(pNode->m_pNext != pToBeDeleted) { pNode = pNode->m_pNext; } // deleted pToBeDeleted pNode->m_pNext = NULL; delete pToBeDeleted; pToBeDeleted = NULL; } } 值得注意的是,为了让代码看起来简洁一些,上面的代码基于两个假设:(1)给定的结点的确在链表中;(2)给定的要删除的结点不是链表的头结点。不考虑第一个假设对代码的鲁棒性是有影响的。至于第二个假设,当整个列表只有一个结点时,代码会有问题。但这个假设不算很过分,因为在有些链表的实现中,会创建一个虚拟的链表头,并不是一个实际的链表结点。这样要删除的结点就不可能是链表的头结点了。当然,在面试中,我们可以把这些假设和面试官交流。这样,面试官还是会觉得我们考虑问题很周到的。
解析
这是一道广为流传的Google面试题,能有效考察我们的编程基本功,还能考察我们的反应速度,更重要的是,还能考察我们对时间复杂度的理解。
在链表中删除一个结点,最常规的做法是从链表的头结点开始,顺序查找要删除的结点,找到之后再删除。由于需要顺序查找,时间复杂度自然就是O(n) 了。
我们之所以需要从头结点开始查找要删除的结点,是因为我们需要得到要删除的结点的前面一个结点。我们试着换一种思路。我们可以从给定的结点得到它的下一个结点。这个时候我们实际删除的是它的下一个结点,由于我们已经得到实际删除的结点的前面一个结点,因此完全是可以实现的。当然,在删除之前,我们需要需要把给定的结点的下一个结点的数据拷贝到给定的结点中。此时,时间复杂度为O(1)。
上面的思路还有一个问题:如果删除的结点位于链表的尾部,没有下一个结点,怎么办?我们仍然从链表的头结点开始,顺便遍历得到给定结点的前序结点,并完成删除操作。这个时候时间复杂度是O(n)。
那题目要求我们需要在O(1)时间完成删除操作,我们的算法是不是不符合要求?实际上,假设链表总共有n个结点,我们的算法在n-1总情况下时间复杂度是O(1),只有当给定的结点处于链表末尾的时候,时间复杂度为O(n)。那么平均时间复杂度[(n-1)*O(1)+O(n)]/n,仍然为O(1)。
转载请注明原文地址:https://kaotiyun.com/show/wRmZ777K
0
程序员面试
相关试题推荐
TheUnitedStatesInterstateHighwaySystemisaninfrastructurefeatofunprecedentedproportions.Notonlydoesitjoinallfi
Americanschoolsaren’texactlyfrozenintime,butconsideringthepaceofchangeinotherareasoflife,ourpublicschoolste
Americanschoolsaren’texactlyfrozenintime,butconsideringthepaceofchangeinotherareasoflife,ourpublicschoolste
定义栈的数据结构,要求添加一个min函数,能够得到栈的最小元素。要求函数min、push以及pop的时间复杂度都是O(1)。
输入一个英文句子,翻转句子中单词的顺序,但单词内字符的顺序不变。句子中单词以空格符隔开。为简单起见,标点符号和普通字母一样处理。例如输入“Iamastudent.”,则输出“student.aamI”。
输入一棵二元查找树,将该二元查找树转换成一个排序的双向链表。要求不能创建任何新的结点,只调整指针的指向。 比如将二元查找树转换成双向链表4=6=8=10=12=14=16。
求最大连续递增数字串(如“ads3sl456789DF3456ld345AA”中的“456789”)
在Excel中,函数ABS(ROUND(-1.478,2))的计算结果是()。A.-1.478B.1.48C.-1.48D.1.5
Excel2000中,列标()A.可以用各种符号表示B.用数字表示C.用字母表示D.可以用中文文字表示
在计算机的应用中,cad是指()。A.计算机辅助制造B.计算机辅助教学C.计算机辅助设计D.计算机辅助测试
随机试题
在缓刑考验期限内,被宣告缓刑的犯罪分子在下列哪些情形中应被撤销缓刑?()
有以下程序:#include#definePT4.5;#defines(x)PT*:x*x;main(){inta=1,b=2;printf("%4.1f\n",s(a+b));}
革命
在定值保险合同中,若保险标的因保险事故导致全损,保险人赔偿的标准是
论述当代大学生如何在学习和生活实践中确立正确的理想信念。
内毒素导致DIC是因为可激活Ⅻ因子,启动内源性凝血系统。
A.低渗性缺水B.高渗性缺水C.等渗性缺水D.高血钾E.低血钾结肠绒毛状腺瘤引起
某单独招标打桩工程编制招标控制价。设计钻孔灌注砼桩50根,桩径φ700mm,设计桩长26m,其中人岩(Ⅳ类)2m,自然地面标高-0.45m,桩顶标高-2.20m。如图所示,砼采用C30现场自拌,根据地质情况土孔砼充盈系数为1.20,岩石孔砼充盈系数为1.0
二级市场的组织形态有两种,一种是交易所,证券的买主和卖主或是其代理人在交易所的一个中心地点见面并进行交易,另一种交易形式是()
Whatisthepurposeofthemeeting?
最新回复
(
0
)