前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >用O(1)的时间复杂度删除单链表中的某个节点

用O(1)的时间复杂度删除单链表中的某个节点

作者头像
Linux云计算网络
发布2018-01-11 10:27:56
8330
发布2018-01-11 10:27:56
举报
文章被收录于专栏:Linux云计算网络

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

代码语言:javascript
复制
struct ListNode
{
      int        m_nKey;
      ListNode*  m_pNext;
};

函数的声明如下:

代码语言:javascript
复制
void DeleteNode(ListNode* pListHead, ListNode* pToBeDeleted);

这是一道广为流传的Google面试题,考察我们对链表的操作和时间复杂度的了解,咋一看这道题还想不出什么较好的解法,但人家把题出在这,肯定是有解法的。一般单链表删除某个节点,需要知道删除节点的前一个节点,则需要O(n)的遍历时间,显然常规思路是不行的。在仔细看题目,换一种思路,既然不能在O(1)得到删除节点的前一个元素,但我们可以轻松得到后一个元素,这样,我们何不把后一个元素赋值给待删除节点,这样也就相当于是删除了当前元素。可见,该方法可行,但如果待删除节点为最后一个节点,则不能按照以上思路,没有办法,只能按照常规方法遍历,时间复杂度为O(n),是不是不符合题目要求呢?可能很多人在这就会怀疑自己的思考,从而放弃这种思路,最后可能放弃这道题,这就是这道面试题有意思的地方,虽看简单,但是考察了大家的分析判断能力,是否拥有强大的心理,充分自信。其实我们分析一下,仍然是满足题目要求的,如果删除节点为前面的n-1个节点,则时间复杂度为O(1),只有删除节点为最后一个时,时间复杂度才为O(n),所以平均的时间复杂度为:(O(1) * (n-1) + O(n))/n = O(1);仍然为O(1).下面见代码:

代码语言:javascript
复制
 1 /* Delete a node in a list with O(1)
 2  * input:    pListHead - the head of list
 3  *            pToBeDeleted - the node to be deleted
 4  */
 5 
 6 struct  ListNode  
 7 {
 8     int            m_nKey;
 9     ListNode*    m_pNext;
10 };
11 
12 void DeleteNode(ListNode *pListHead, ListNode *pToBeDeleted)
13 {
14     if (!pListHead || !pToBeDeleted)
15         return;
16     
17     if (pToBeDeleted->m_pNext != NULL) { 
18         ListNode *pNext = pToBeDeleted->m_pNext;
19         pToBeDeleted->m_pNext = pNext->m_pNext;
20         pToBeDeleted->m_nKey = pNext->m_nKey;
21 
22         delete pNext;
23         pNext = NULL;
24     }
25     else { //待删除节点为尾节点
26         ListNode *pTemp = pListHead;
27         while(pTemp->m_pNext != pToBeDeleted) 
28             pTemp = pTemp->m_pNext;
29         pTemp->m_pNext = NULL;
30 
31         delete pToBeDeleted;
32         pToBeDeleted = NULL;
33     }
34 }
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2014-10-09 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档