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

相关文章

来自专栏kevindroid

leetcode538 Convert BST to Greater Tree

17640
来自专栏陈树义

Java ConcurrentModificationException异常原因和解决方法

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

38940
来自专栏一个会写诗的程序员的博客

List.remove 报错 UnsupportedOperationException

Java中List.remove(removeRange,clear类似) 报出 UnsupportedOperationException 的错误。原来该Li...

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

Q112 Path Sum

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

36370
来自专栏趣学算法

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

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

13130
来自专栏尾尾部落

[剑指offer] 按之字形顺序打印二叉树

请实现一个函数按照之字形打印二叉树,即第一行按照从左到右的顺序打印,第二层按照从右至左的顺序打印,第三行按照从左到右的顺序打印,其他行以此类推。

9720
来自专栏猿人谷

顺序线性表

线性表的顺序表示和实现 线性表的顺序表示指的是用一组地址连续的存储单元依次存储线性表的数据元素。 线性表的第一个数据元素a1的存储位置,通常称作线性表的起始位置...

25150
来自专栏猿人谷

单链表反转的分析及实现

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

1.6K100
来自专栏老马说编程

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

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

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

Leetcode 34 Search for a Range

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

22290

扫码关注云+社区

领取腾讯云代金券