剑指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 条评论
登录 后参与评论

相关文章

来自专栏日常分享

通过BitSet完成对单词使用字母的统计

  BitSet类实现了一组位或标记(flag),这些位可被分别设置或清除。当需要跟踪一组布尔值时,这种类很有用。

652
来自专栏Bingo的深度学习杂货店

Q112 Path Sum

Given a binary tree and a sum, determine if the tree has a root-to-leaf path suc...

3367
来自专栏趣学算法

数据结构 第12讲 二叉树的层次遍历

二叉树的遍历一般有先序遍历、中序遍历和后序遍历,这三种遍历比较简单。今天我们讲二叉树的另一种遍历方式,层次遍历。即按照层次进行遍历。如图1所示:

793
来自专栏尾尾部落

[剑指offer] 重建二叉树

输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6...

881
来自专栏陈树义

Java ConcurrentModificationException异常原因和解决方法

Java ConcurrentModificationException异常原因和解决方法   在前面一篇文章中提到,对Vector、ArrayList在迭代的...

3654
来自专栏老马说编程

(32) 剖析日期和时间 / 计算机程序的思维逻辑

本节和下节,我们讨论在Java中如何进行日期和时间相关的操作。 日期和时间是一个比较复杂的概念,Java API中对它的支持不是特别好,有一个第三方的类库反而特...

18610
来自专栏猿人谷

单链表反转的分析及实现

我先画一个单链表,这个单链表有4个元素。我的思路就是,每次把第二个元素提到最前面来。比如下面是第一次交换,我们先让头结点的next域指向结点a2,再让结点a1...

64810
来自专栏kevindroid

leetcode538 Convert BST to Greater Tree

1534
来自专栏计算机视觉与深度学习基础

Leetcode 34 Search for a Range

Given a sorted array of integers, find the starting and ending position of a gi...

1929
来自专栏xingoo, 一个梦想做发明家的程序员

程序猿的日常——Java中的集合列表

列表对于日常开发来说实在是太常见了,以至于很多开发者习惯性的用到数组,就来一个ArrayList,根本不做过多的思考。其实列表里面还是有很多玩法的,有时候玩不...

1926

扫码关注云+社区