JZ-069-在 O(1) 时间内删除链表节点
2024-09-06 10:46:32
在 O(1) 时间内删除链表节点
题目描述
在 O(1) 时间内删除链表节点。
方案：如果该节点不是尾节点，那么可以直接将下一个节点的值赋给该节点，然后令该节点指向下下个节点，再删除下一个节点，时间复杂度为 O(1)。否则，就需要先遍历链表，找到节点的前一个节点，然后让前一个节点指向 null，时间复杂度为 O(N)。
题目链接: 在 O(1) 时间内删除链表节点
代码
/**
* 在 O(1) 时间内删除链表节点
*/
public class Jz69 {
/**
* 方案：
* 如果该节点不是尾节点，那么可以直接将下一个节点的值赋给该节点，然后令该节点指向下下个节点，再删除下一个节点，时间复杂度为 O(1)。
* 否则，就需要先遍历链表，找到节点的前一个节点，然后让前一个节点指向 null，时间复杂度为 O(N)。
*
* @param head
* @param tobeDelete
* @return
*/
public ListNode deleteNode(ListNode head, ListNode tobeDelete) {
if (head == null || tobeDelete == null) {
return null;
}
if (tobeDelete.next != null) {
// 要删除的节点不是尾结点
ListNode next = tobeDelete.next;
tobeDelete.val = next.val;
tobeDelete.next = next.next;
} else {
if (head == tobeDelete) {
// 只有一个节点
head = null;
} else {
ListNode cur = head;
while (cur.next != tobeDelete) {
cur = cur.next;
}
cur.next = null;
}
}
return head;
}
public static void main(String[] args) {
}
}
【每日寄语】 窦燕山，有义方；教五子，名俱扬。
最新文章
- python爬虫学习(10) —— 专利检索DEMO
- wordpress多站点环境设置上传附件大小
- Enterprise Solution 2.2 开发帮助文档集合
- 【Python】Django 聚合 Count与Sum用法，注意点
- BZOJ1075 : [SCOI2007]最优驾车drive
- html部分---样式表，选择器；
- Spring MVC 3.0.5+Spring 3.0.5+MyBatis3.0.4全注解实例详解（一）
- 【bzoj】1026: [SCOI2009]windy数
- JavaScript Window Screen
- C++虚函数在内存中的实现
- Effective C++ 条款24
- Prism for Xamarin.Forms
- <魔域>按键精灵脚本
- 75.纯 CSS 创作一支摇曳着烛光的蜡烛
- linux学习笔记-时间配置综述
- redis跳跃表
- Linux系统性能监控工具：tsar 安装、配置、以及使用
- Browsersync结合gulp和nodemon实现express全栈自动刷新
- Go 2 Draft Designs
- CloudSetuper