首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
给定链表的头指针和一个结点指针,在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
133
问题
给定链表的头指针和一个结点指针,在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
程序员面试
相关试题推荐
[A]Theperson-skillsmatchapproachtoselection[B]Theimpactsofbadselectiondecisions[C]Theimportanceofstructu
输入一个整数数组,判断该数组是不是某二元查找树的后序遍历的结果。如果是返回true,否则返回false。例如输入5、7、6、9、11、10、8,由于这一整数序列是如下树的后序遍历结果:8/\610
2005年11月金山笔试题。编码完成下面的处理函数。函数将字符串中的字符’*’移到串的前部分,前面的非’*’字符后移,但不能改变非’*’字符的先后顺序,函数返回串中字符’*’的数量。如原始串为:ab**cd**e*12,处理后为*****abcde12,函
定义字符串的左旋转操作:把字符串前面的若干个字符移动到字符串的尾部。如把字符串abcdef左旋转2位得到字符串cdefab。请实现字符串左旋转的函数。要求时间对长度为n的字符串操作的复杂度为O(n),辅助内存为O(1)。
什么是ASP.net中的用户控件
在即时通讯工具MSN中,从当前界面开始,把自己的邮箱注册为“Passport”,已知邮箱地址为:ccty@163.com,密码设置为116116,密码提示问题为:你最喜欢的历史人物?毛泽东,注册检查框内的字符按照图片上给的输入,字符输入区分大小写,其余选项
若要改变打印时的纸张大小,正确的是()A.[页面设计]对话框中的[纸张大小]B.[页面设计]对话框中的[中文版式]C.[版式]对话框中的[中文版式]D.[工具]对话框中的[选项]
一个软件的架构设计是随着技术的不断进步而不断变化的。以编译器为例,其主流架构经历了管道—过滤器到数据共享为中心的转变过程。以下关于编译器架构的叙述中,错误的是______。
在数据库系统中,“事务”是访问数据库并可能更新各种数据项的一个程序执行单元。为了保证数据完整性,要求数据库系统维护事务的原子性、一致性、隔离性和持久性。针对事务的这4种特性,考虑以下的架构设计场景:假设在某一个时刻只有一个活动的事务,为了保证事务
在实际应用中,用户通常依靠评价程序来测试系统的性能。以下评价程序中,(16)的评测准确程度最低。事务处理性能委员会(TransactionProcessingPerformanceCouncil,TPC)是制定商务应用基准程序(Benchmark)标
随机试题
根据水利部《水库大坝安全鉴定办法》(水建管〔2003〕271号),水库大坝首次安全鉴定应在竣工验收后()年内进行。
根据症状可诊断为:最合适的辨证为:
亚硫酸钠在显影液中的作用是
下列金融工具可作为利率期权的基础资产的有( )。
按照我国《劳动法》的规定,依法解除劳动合同的权利属于()。
总机构和分支机构处于不同税率地区的,应当按照法律规定计算与分摊应纳税所得额。下列说法正确的有()。
学校不得使未成年学生在危及人身安全的校舍和其他教学设施中活动,否则就侵犯了学生的()
党的____________是党的根本性建设,决定党的建设方向和效果,是党的建设理论和实践的重大创新。
下列叙述中正确的是()。
Nowonlineprovisionistransforminghighereducation,givingthebestuniversitiesachancetowidentheircatch,openingnewo
最新回复
(
0
)