文档章节

剑指Offer(java版):在O(1)时间删除链表节点

一贱书生
 一贱书生
发布于 2016/07/19 20:27
字数 772
阅读 15
收藏 0

题目:给定单向链表的头指针和一个节点指针,定义一个函数在O(1)时间删除该节点。

在单向链表中删除一个节点,最常规的方法无疑是从链表的头结点开始,顺序遍历查找要删除的节点,并在链表中删除该节点。

比如图a所表示的链表中,我们要删除节点i,可以从链表的头节点a开 始顺序遍历,发现节点h的m_PNext指向要删除的节点i,于是我们可疑把节点h的m_PNext指向i的下一个节点即为j。指针调整之后,我们就可以 安全地删除节点i并保证链表没有断开。这种思路由于需要顺序查找,时间复杂度自然就是O(n)了。

之所以要从头开始查找,是因为我们需要得到被删除的节点的前面一个节点。在单向链表中,节点中没有前一个节点的指针,所以只好从链表的头结点开始顺序查找。

那是不是一定要得到被删除的节点的前一个节点呢?答案是否定的。我们可疑很方面地得到要删除的节点的下一个节点。如果我们把下一个节点的内容复制到要删除的节点上覆盖原有的内容,再把下一个节点删除,那是不是就相当于把当前要删除的节点删除了?

我们还是以前面的例子来分析这种思路,我们要删除的节点i,先把i的下一个节点j的内容复制到i,然后把i的指针指向节点j的下一个节点。此时再删除节点j,其效果刚好是把节点i给删除了(图c)

上述问题还有一个问题;如果要删除的节点位于链表的尾部,那么它就没有下一个节点,怎么办?我们让然从链表的头节点开始,顺序遍历得到该节点的前序节点,并完成删除操作。

最后需要注意的是,如果链表中只有一个节点,而我们又要 链表的头节点(也是尾节点),此时我们在删除节点之后,还需要把链表的头节点设置为NULL。

有了这种思路,现在我们是实现代码:

package cglib;

class ListNode
{ int data;
  ListNode nextNode;
}
public class DeleteNode {
    public static void main(String[] args) {
        ListNode head=new ListNode();
        ListNode second=new ListNode();
        ListNode third=new ListNode();
        head.nextNode=second;
        second.nextNode=third;
        head.data=1;
        second.data=2;
        third.data=3;
        DeleteNode p13=new DeleteNode();
        p13.deleteNode(head, second);
        
        System.out.println(head.nextNode.data);
        }
        public void deleteNode(ListNode head,ListNode deListNode){
        if(deListNode==null||head==null){
        return;
        }
        if(head==deListNode){//只有一个结点,删除头结点
        head=null;
        }
        else{
        if(deListNode.nextNode==null){//删除尾结点,顺序遍历得到前一个结点
        ListNode pointListNode=head;//从头结点开始
        while(pointListNode.nextNode.nextNode!=null){
        pointListNode=pointListNode.nextNode;
        }
        pointListNode.nextNode=null;
        }
        else{ //删除的不是尾结点
        deListNode.data=deListNode.nextNode.data;//复制
        deListNode.nextNode=deListNode.nextNode.nextNode;
        }
        }
        }
}


输出:

3

© 著作权归作者所有

一贱书生
粉丝 19
博文 724
码字总数 600123
作品 0
私信 提问
面试:用 Java 逆序打印链表

面试:用 Java 逆序打印链表 昨天的 Java 实现单例模式 中,我们的双重检验锁机制因为指令重排序问题而引入了 关键字,不少朋友问我,到底为啥要加 这个关键字呀,而它,到底又有什么神奇的作...

nanchen2251
2018/07/03
0
0
数据结构与算法(4)——优先队列和堆

前言:题图无关,接下来开始简单学习学习优先队列和堆的相关数据结构的知识; 前序文章: 数据结构与算法(1)——数组与链表(https://www.jianshu.com/p/7b93b3570875) 数据结构与算法(2)—...

我没有三颗心脏
2018/07/12
0
0
源码之LinkedList 单双向链表介绍

链表 单向链表 单链表的特点: 最后一个节点的next为null(闭环链表指向第一个元素) 只可一个方向遍历 双向链表 特点: 最后一个节点的next为null(闭环链表指向第一个元素) 可双向遍历(从头部...

yimingkeji
01/07
0
0
[算法总结] 一文搞懂面试链表题

本文首发于我的个人博客:尾尾部落 链表是面试过程中经常被问到的,这里把剑指offer 和 LeetCode 中的相关题目做一个汇总,方便复习。 1. 在 O(1) 时间删除链表节点 题目描述:给定单向链表的...

繁著
2018/08/28
0
0
数据结构与算法(3)——树(二叉、二叉搜索树)

前言:题图无关,现在开始来学习学习树相关的知识 前序文章: 数据结构与算法(1)——数组与链表(https://www.jianshu.com/p/7b93b3570875) 数据结构与算法(2)——栈和队列(https://www.ji...

我没有三颗心脏
2018/07/11
0
0

没有更多内容

加载失败,请刷新页面

加载更多

利用mybatis generator生成实体类、Mapper接口以及对应的XML文件

项目中通常会遇到数据的持久化,如果是采用mybatis的orm,就会涉及到生成xml的问题,刚好mybatis官网提供了这么个插件MyBatis Generator,效果简直是棒呆。 1. 首先需要在build.gradle文件中...

啊哈关关
今天
2
0
SpringSocial相关的知识点

使用SprigSocial开发第三方登录 核心类 ServiceProvider(AbstractOauth2ServiceProvider):主要负责实现server提供商(例如QQ,微信等共有的东西),默认实现类是AbstractOauth2ServiceProvider...

chendom
今天
3
0
Java并发之AQS详解

一、概述   谈到并发,不得不谈ReentrantLock;而谈到ReentrantLock,不得不谈AbstractQueuedSynchronizer(AQS)!   类如其名,抽象的队列式的同步器,AQS定义了一套多线程访问共享资源...

群星纪元
昨天
4
0
Fabric-sdk-java最新教程

Fabric Java SDK是Fabric区块链官方提供的用于Java应用开发的SDK,全称为Fabric-sdk-java,网上可用资料不多,本文列出了精心整理的针对Fabric Java SDK的最新精选教程。 如果希望快速掌握F...

汇智网教程
昨天
3
0
react 子组件监听props 变化

componentWillReceiveProps //已经被废弃 getDerivedStateFromProps// 推荐使用//如果条件不存在必须要返回null static getDerivedStateFromProps(props, current_stat...

一箭落旄头
昨天
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部