热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

时间复杂度为O(1)的删除链表结点方法

这是一道广为流传的Google面试题,能有效考察我们的编程基本功,还能考察我们的反应速度,更重要的是,还能考察我们对时间复杂度的理解。在链表中删除一个结点,最常规的做法是从链表的头结点开始,顺序查找要删除的结点,找到之后再删除。由于需要顺序查找,时间复杂度自然就是O(n)了。

给定链表的头指针和一个结点指针,在O(1)时间删除该结点。链表结点的定义如下:

struct ListNode
{
      int        m_nKey;
      ListNode*  m_pNext;
};

函数的声明如下:

void DeleteNode(ListNode* pListHead, ListNode* pToBeDeleted);

这是一道广为流传的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)。

基于前面的分析,我们不难写出下面的代码。

///////////////////////////////////////////////////////////////////////
// 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)给定的要删除的结点不是链表的头结点。不考虑第一个假设对代码的鲁棒性是有影响的。至于第二个假设,当整个列表只有一个结点时,代码会有问题。但这个假设不算很过分,因为在有些链表的实现中,会创建一个虚拟的链表头,并不是一个实际的链表结点。这样要删除的结点就不可能是链表的头结点了。当然,在面试中,我们可以把这些假设和面试官交流。这样,面试官还是会觉得我们考虑问题很周到的。

PS:假设要删除A节点,A.next==B。则删除B,并将B的值赋给A,这样就等于删除了A节点。

本文地址:http://www.nowamagic.net/librarys/veda/detail/261,欢迎访问原出处。


推荐阅读
  • 采用IKE方式建立IPsec安全隧道
    一、【组网和实验环境】按如上的接口ip先作配置,再作ipsec的相关配置,配置文本见文章最后本文实验采用的交换机是H3C模拟器,下载地址如 ... [详细]
  • 丽江客栈选择问题
    本文介绍了一道经典的算法题,题目涉及在丽江河边的n家特色客栈中选择住宿方案。两位游客希望住在色调相同的两家客栈,并在晚上选择一家最低消费不超过p元的咖啡店小聚。我们将详细探讨如何计算满足条件的住宿方案总数。 ... [详细]
  • 本文介绍了数据库体系的基础知识,涵盖关系型数据库(如MySQL)和非关系型数据库(如MongoDB)的基本操作及高级功能。通过三个阶段的学习路径——基础、优化和部署,帮助读者全面掌握数据库的使用和管理。 ... [详细]
  • Coursera ML 机器学习
    2019独角兽企业重金招聘Python工程师标准线性回归算法计算过程CostFunction梯度下降算法多变量回归![选择特征](https:static.oschina.n ... [详细]
  • 智能车间调度研究进展
    本文综述了基于强化学习的智能车间调度策略,探讨了车间调度问题在资源有限条件下的优化方法。通过数学规划、智能算法和强化学习等手段,解决了作业车间、流水车间和加工车间中的静态与动态调度挑战。重点讨论了不同场景下的求解方法及其应用前景。 ... [详细]
  • 在使用Node.js运行时环境的Next.js应用程序部署过程中,遇到了与目录文件数量相关的错误。本文将详细探讨该问题及其解决方案。 ... [详细]
  • 二维几何变换矩阵解析
    本文详细介绍了二维平面上的三种常见几何变换:平移、缩放和旋转。通过引入齐次坐标系,使得这些变换可以通过统一的矩阵乘法实现,从而简化了计算过程。文中不仅提供了理论推导,还附有Python代码示例,帮助读者更好地理解这些概念。 ... [详细]
  • 本文详细介绍了福昕软件公司开发的Foxit PDF SDK ActiveX控件(版本5.20),并提供了关于其在64位Windows 7系统和Visual Studio 2013环境下的使用方法。该控件文件名为FoxitPDFSDKActiveX520_Std_x64.ocx,适用于集成PDF功能到应用程序中。 ... [详细]
  • ZooKeeper集群脑裂问题及其解决方案
    本文深入探讨了ZooKeeper集群中可能出现的脑裂问题,分析其成因,并提供了多种有效的解决方案,确保集群在高可用性环境下的稳定运行。 ... [详细]
  • Java 实现二维极点算法
    本文介绍了一种使用 Java 编程语言实现的二维极点算法。该算法用于从一组二维坐标中筛选出极点,适用于需要处理几何图形和空间数据的应用场景。文章不仅详细解释了算法的工作原理,还提供了完整的代码示例。 ... [详细]
  • 本次挑战涉及数组截断操作,初看似乎简单,但实际上考察了对数组切片方法的理解与应用。本文将详细解析该算法的实现逻辑,并提供多个示例以加深理解。 ... [详细]
  • 本文深入探讨了Memcached的内存管理机制,特别是其采用的Slab Allocator技术。该技术通过预分配不同大小的内存块来有效解决内存碎片问题,并确保高效的数据存储与检索。文中详细描述了Slab Allocator的工作原理、内存分配流程以及相关的优化策略。 ... [详细]
  • 华为智慧屏:超越屏幕尺寸的智能进化
    继全球发布后,华为智慧屏于9月26日在上海正式亮相,推出65英寸和75英寸版本。该产品不仅在屏幕尺寸上有所突破,更在性能和智能化方面实现了显著提升。 ... [详细]
  • 本文介绍如何利用栈数据结构在C++中判断字符串中的括号是否匹配。通过顺序栈和链栈两种方式实现,并详细解释了算法的核心思想和具体实现步骤。 ... [详细]
  • Redux入门指南
    本文介绍Redux的基本概念和工作原理,帮助初学者理解如何使用Redux管理应用程序的状态。Redux是一个用于JavaScript应用的状态管理库,特别适用于React项目。 ... [详细]
author-avatar
176精品传奇双线
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有