给定单向链表的头指针和一个节点指针,定义一个函数在O(1)时间内删除该节点。

 struct ListNode {
int val;
ListNode *next;
};
 void DeleteNode(ListNode* &pListHead, ListNode* pToBeDeleted):
if (!pListNode || !pToBeDeleted) {
return;
} if (pToBeDeleted->next != nullptr) {//要删除的节点不是尾节点
ListNode* pNode = pToBeDeleted->next;
pToBeDeleted->val = pNode->val;
pToBeDeleted->next = pNode->next; delete pNode;
pNode = nullptr;
} else if (pListHead == pToBeDeleted) {//链表只有一个节点 delete pToBeDeleted;
pToBeDeleted = nullptr;
pListHead = nullptr;
} else {//链表有多个节点,删除尾节点
ListNode* pNode = pListHead;
while (pNode->next != pToBeDeleted) {
pNode = pNode->next;
}
pNode->next = nullptr;
delete pToBeDeleted;
pToBeDeleted = nullptr;
}

时间复杂度分析:对于n-1个非尾节点来说,都可以在O(1)时间内删除节点。对于删除尾节点,时间复杂度是O(n)。

因此平均时间复杂度为[(n - 1) * O(1) + O(n)] / n

最新文章

  1. 【转】MySQL 高可用架构在业务层面的分析研究
  2. vim帮助手册汉化
  3. ActiveMQ Exception: java.io.EOFException: Chunk stream does not exist
  4. Maven仓库—Nexus环境搭建及简单介绍
  5. struts2标签详解
  6. 请问view controller scene,该如何删除
  7. Android设置TextView显示一行或多行
  8. HTML 表格、区块、其他常用控件
  9. (原)前端知识杂烩(meta系列)
  10. JVM学习笔记一:Java运行时数据区域
  11. C#源码发送简单的HTTP请求
  12. 有意思的flex 色子布局
  13. sencha touch list + carousel scrollable(与其他控件共用滚动条)
  14. 33. Search in Rotated Sorted Array(二分查找)
  15. ACM大牛的BLOG(转)
  16. Git如何设置多个用户
  17. CentOS 7 下编译安装lnmp之nginx篇详解
  18. SCOI2014极水的题解- -
  19. 《python学习手册》第34章 异常对象
  20. 第十四篇:Apriori 关联分析算法原理分析与代码实现

热门文章

  1. Python与CSV文件(CSV模块)
  2. join的源码
  3. c++函数相关
  4. IDEA使用一套代码启动多个应用
  5. Electron-Vue工程初始化,以及需要掌握的相关知识
  6. HDU4497 GCD and LCM(数论,质因子分解)
  7. MYSQL,分别用一条语句交换两列的值与两行的值
  8. Django学习之序列化和信号
  9. WPF WebBrowser 加载 html ,出现安全警告, 运行 脚本和 activeX 控件,
  10. vue 请求完接口后执行方法