剑指offer代码分析——面试题13在O(1)内删除链表结点

本题详细解析都已在代码中注释了:

/**
 * 给一个单链表,头指针为first,请用O(1)时间删除其中节点p
 * @author chibozhou
 */
public class DeleteNode {

	/**
	 * 分析:
	 * 删除单链表中的某一节点常规做法是:
	 * 从头开始扫描单链表,找到p节点的前一个节点q,然后做以下操作:
	 * 	q.next = p.next;
	 * 	p = null;
	 * 
	 * 这种方法扫描了单链表,因此时间复杂度是O(n)。
	 * 下面我们寻找时间复杂度O(1)的方法。
	 */
	
	/**
	 * 方法一之所以耗时,是因为它在寻找p的前一个结点采用了遍历,
	 * 因此,只要提升寻找前一个结点的效率,就能提升整个算法的效率。
	 * 那么,是否有办法能够在O(1)时间内找到前一个结点呢?
	 */
	
	/**
	 * 厉害的方法如下:
	 * 将p后继结点的数据复制到p中,再删除p的后继结点即可!代码如下:
	 */
	public static <T> boolean deleteNode(Node<T> first, Node<T> p){
		//若链表为空
		if(first==null){
			System.out.println("链表为空!");
			return false;
		}
		
		//若p是最后一个结点,则只能遍历寻找p的前一个结点
		//解析:上述复制后继结点删除p的方法,在删除过程中,需要用到p.next=p.next.next;
		//若p已经是最后一个结点,则上述语句就会出现空指针异常,因此p为最后一个结点的情况要单独判断.
		if(p.next == null){
			Node<T> q = p;
			while(p.next != null){
				q = p;
				p = p.next;
			}
			q.next = p.next;
			p = null;
		}
		
		//若p不是最后一个结点,则将p后继结点的数据复制到p中,再删除p的后继结点
		//解析:单链表是一种用于存储数据的物理结构,从逻辑上看和数组一样。
		//要删除一个结点,从逻辑上看就是删除一个序列的某一个数据。因此,从逻辑上看,
		//只要两个结点的数值相同,就认为这两个结点是相等的。
		//因此,采用这种复制后继结点的方式删除结点,虽然删除后结点的存储位置发生了变化,
		//但从逻辑角度看,只是删除了序列中的一个数。
		if(p.next != null){
			p.data = p.next.data;
			p.next = p.next.next;
		}
		
		return true;
	}
	
}

/**
 * 定义结点 
 */
class Node<T>{
	public T data;
	public Node<T> next;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏python成长之路

lambda函数常见用法

1565
来自专栏项勇

笔记23 | 复习for/while/do...while的几种循环用法

1447
来自专栏数据结构与算法

P1198 [JSOI2008]最大数

题目描述 现在请求你维护一个数列,要求提供以下两种操作: 1、 查询操作。 语法:Q L 功能:查询当前数列中末尾L个数中的最大的数,并输出这个数的值。 限制:...

2679
来自专栏简书专栏

Python入门2

定义:列表是最常用的python数据类型,一个列表中可以存储多个不同类型的数据。 语法:[]可以是number、string、bool等

451
来自专栏Android机动车

数据结构学习笔记——线性表(下)

了解过线性表的链式存储结构以后,有人就想出来用数组来代替指针,来描述单链表。看看他们是怎么做到的。

351
来自专栏云霄雨霁

排序----选择排序

1370
来自专栏Golang语言社区

Go 语言的基本数据类型

0)变量声明 var 变量名字 类型 = 表达式 例: var num int = 10 复制代码 其中“类型”或“= 表达式”两个部分可以省略其中的一个。 1...

35511
来自专栏python3

python3--基础数据类型

切片就是通过索引(索引:索引:步长)截取字符串的一段,形成新的字符串(原则就是顾头不顾尾)

532
来自专栏我的博客

插入排序

原理: 1. 从第一个元素开始,该元素可以认为已经被排序 2. 取出下一个元素,在已经排序的元素序列中从后向前扫描 3. 如果该元素(已排序)大于新元素,...

2276
来自专栏猿人谷

数组和链表的区别

数组: 数组是将元素在内存中连续存放,由于每个元素占用内存 相同,可以通过下标迅速访问数组中任何元素。但是如果要在数组中增加一个元素,需要移动大量元素,在内...

1707

扫描关注云+社区