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