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

从分析与思考中找到答案
服务器君一共花费了155.922 ms进行了4次数据库查询,努力地为您提供了这个页面。
试试阅读模式?希望听取您的建议

给定链表的头指针和一个结点指针,在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,欢迎访问原出处。

不打个分吗?

转载随意,但请带上本文地址:

http://www.nowamagic.net/librarys/veda/detail/261

如果你认为这篇文章值得更多人阅读,欢迎使用下面的分享功能。
小提示:您可以按快捷键 Ctrl + D,或点此 加入收藏

大家都在看

阅读一百本计算机著作吧,少年

很多人觉得自己技术进步很慢,学习效率低,我觉得一个重要原因是看的书少了。多少是多呢?起码得看3、4、5、6米吧。给个具体的数量,那就100本书吧。很多人知识结构不好而且不系统,因为在特定领域有一个足够量的知识量+足够良好的知识结构,系统化以后就足以应对大量未曾遇到过的问题。

奉劝自学者:构建特定领域的知识结构体系的路径中再也没有比学习该专业的专业课程更好的了。如果我的知识结构体系足以囊括面试官的大部分甚至吞并他的知识结构体系的话,读到他言语中的一个词我们就已经知道他要表达什么,我们可以让他坐“上位”毕竟他是面试官,但是在知识结构体系以及心理上我们就居高临下。

所以,阅读一百本计算机著作吧,少年!

《C程序设计语言(第2版新版)》 克尼汉 (作者), 等 (作者, 译者), 徐宝文 (译者)

《C程序设计语言》(第2版新版)是由C语言的设计者Brian W.Kernighan和Dennis M.Ritchie编写的一部介绍标准C语言及其程序设计方法的权威性经典著作。全面、系统地讲述了C语言的各个特性及程序设计的基本方法,包括基本概念,类型和表达式、控制流、函数与程序结构、指针与数组、结构、输入与输出、UNIX系统接口、标准库等内容。

更多计算机宝库...