用O(1)的时间复杂度删除单链表中的某个节点
节点 时间 删除 某个 表中 复杂度 单链
2023-09-14 09:00:07 时间
给定链表的头指针和一个结点指针,在O(1)时间删除该结点。链表结点的定义如下:
struct ListNode { int m_nKey; ListNode* m_pNext; };
函数的声明如下:
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).下面见代码:
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 }
我的公众号 「Linux云计算网络」(id: cloud_dev),号内有 10T 书籍和视频资源,后台回复 「1024」 即可领取,分享的内容包括但不限于 Linux、网络、云计算虚拟化、容器Docker、OpenStack、Kubernetes、工具、SDN、OVS、DPDK、Go、Python、C/C++编程技术等内容,欢迎大家关注。
相关文章
- 利用jinterface在java和erlang节点之间通讯
- 关于web.config中<customErrors>节点说明
- js获取节点和编辑的方法
- App.config和Web.config配置文件的自定义配置节点
- 复制Hadoop目录至其他节点时的注意点
- Storm单节点部署及启动
- 基于改进蚁狮AALO算法优化电网GIPFC研究【IEEE 30节点】(Matlab代码实现)
- GaussDB(DWS)集群中寻找节点CPU占用高的语句
- 【Groovy】自定义 Xml 生成器 BuilderSupport ( 创建 XmlNode 节点 | 管理 XmlNode 节点并将根节点转为 Xml 信息 | 完整代码示例 )
- 【Groovy】自定义 Xml 生成器 BuilderSupport ( setParent 方法中设置父节点与子节点关系 )
- Merkle 树——空间换时间,分而治之的hash表,通过根节点是由它的两个子节点内容的哈希值组成来校验数据完整性,定位篡改的数据位置
- RK3399平台开发系列讲解(应用开发篇)1.3、ADC节点数据的读取