Java实现删除排序链表中的重复元素的方法

2024-08-20 01:11:38

给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。

示例 1:

输入: 1->1->2
输出: 1->2
示例 2:

输入: 1->1->2->3->3
输出: 1->2->3

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *   int val;
 *   ListNode next;
 *   ListNode(int x) { val = x; }
 * }
 */
class Solution {
   public ListNode deleteDuplicates(ListNode head) {
    if(head == null || head.next == null){
      return head;
    }
    head.next = deleteDuplicates(head.next);
    if(head.val == head.next.val) head = head.next;
    return head;
  }
}

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持我们。

java链表应用--基于链表实现队列详解（尾指针操作）

本文实例讲述了java基于链表实现队列.分享给大家供大家参考,具体如下: 在开始栈的实现之前,我们再来看看关于链表的只在头部进行的增加.删除.查找操作,时间复杂度均为O(1). 一.链表改进分析对于队列这种数据结构,需要在线性结构的一端插入元素,另外一端删除元素.因此此时基于链表来实现队列,则有一端的时间复杂度为O(n).因此我们不能使用之前已经实现的链表结构,我们需要改进我们的链表.思路如下: 1.参考在链表头部删除.增加元素的时间复杂度为O(1)的思路,我们在链表的尾部设立一个Node型的
Java均摊复杂度和防止复杂度的震荡原理分析

本文实例讲述了Java均摊复杂度和防止复杂度的震荡.分享给大家供大家参考,具体如下: 关于上一节封装数组的简单复杂度分析方法中我们对添加操作的时间复杂度归结为O(n)是考虑了扩容操作(resize)在内的.就addLast(e)操作而言,时间复杂度为O(1),在考虑最坏情况下,每次添加均会触发扩容操作,需要移动n个元素,因此此时addLast操作的时间复杂度为O(n). (1)addLast(e)均摊时间复杂度分析 resize(n) O(n) 假设当前capacity=8,并且每一次添加操
用Java实现一个静态链表的方法步骤

什么是静态链表? 对于线性链表,也可用一维数组来进行描述.这种描述方法便于在没有指针类型的高级程序设计语言中使用链表结构. 用数组描述的链表,即称为静态链表. 在C语言中,静态链表的表现形式即为结构体数组,结构体变量包括数据域data和游标CUR. 静态链表的节点数据域:用于存储数据元素的值游标:即数组下标,表示直接后继元素所在数组中的位置 public class StaticLinkedListNode<T> { public T data; // 数据 public int curs
Java底层基于链表实现集合和映射--集合Set操作详解

本文实例讲述了Java底层基于链表实现集合和映射--集合Set操作.分享给大家供大家参考,具体如下: 在Java底层基于二叉搜索树实现集合和映射中我们实现了底层基于二叉搜索树的集合,本节就底层如何基于链表实现进行学习,注意:此处的链表是之前自己封装的. 1.集合set相关功能 1.1 add()的不同用于链表本身没有去重的效果,因此我们在做基于链表的集合时,需要对add()方法做一下特殊处理,如下增加一个判断即可. @Override public void add(E e) { if (!l
Java链表中添加元素的原理与实现方法详解

本文实例讲述了Java链表中添加元素的原理与实现方法.分享给大家供大家参考,具体如下: 1.链表中头节点的引入 1.1基本的链表结构: 1.2对于链表来说,若想访问链表中每个节点则需要把链表的头存起来,假如链表的头节点为head,指向链表中第一个节点,如图: 1.3使用代码表示此时的链表 //定义头节点 private Node head; //节点个数 private int size; //无参数构造函数 public LinkedList() { head = null; size = 0
Java基于二分搜索树、链表的实现的集合Set复杂度分析实例详解

本文实例讲述了Java基于二分搜索树.链表的实现的集合Set复杂度分析.分享给大家供大家参考,具体如下: 两种集合类的复杂度分析在Java底层基于二叉搜索树实现集合和映射和Java底层基于链表实现集合和映射中以二分搜索树和链表作为底层实现了集合Set,在本节就两种集合类的复杂度分析进行分析: 测试内容:Java底层基于二叉搜索树实现集合和映射和Java底层基于链表实现集合和映射中使用的书籍. 测试方法:测试两种集合类查找单词所用的时间 //创建一个测试方法 Set<String> set:
Java基于链表实现栈的方法详解

本文实例讲述了Java基于链表实现栈的方法.分享给大家供大家参考,具体如下: 在上几小节中我们实现了基本的链表结构,并在上一节的底部给出了有关链表的源码,此处在贴一次吧,猛戳在开始栈的实现之前,我们再来看看关于链表的只在头部进行的增加.删除.查找操作,时间复杂度均为O(1),基于链表的这几个优势,我们在此基础上实现栈. 前言,在写本小节之前,我们已经实现了一个基于静态数组的栈,转到查看.此处我们实现基于链表的栈. 1.链表类拷贝到Stack 包下: 在实现基于静态数组的栈的时候,我们已经新建了
Java链表（Linked List）基本原理与实现方法入门示例

本文实例讲述了Java链表(Linked List)基本原理与实现方法.分享给大家供大家参考,具体如下: 在分析链表之前,我们先来对之前的动态数组.栈.队列总结一下: (1)底层依托于静态数组 (2)依靠resize解决固定容量问题 (3)是一种假的的动态数据结构 1.什么是链表可以从以下两个部分来理解什么是链表 (1)最简单的动态数据结构,是一种真正的动态数据结构: (2)是一种数据的存储方式,数据存储在"节点"(Node)中 1.1结构基本代码: class Node{ E e;
Java链表的天然递归结构性质图文与实例分析

本文实例分析了Java链表的天然递归结构性质.分享给大家供大家参考,具体如下: 有关链表,参考之前的文章学习. 要求:使用递归删除链表中指定的所有元素值. 一.图文分析假设有这么一个链表,如下图: 分析:基于链表的宏观语意(递归是问题更小的子过程)进行分析我们可以把上述链表看成是一个头结点后面挂接了一个更小的链表组成,如下图: 此时我们可以把链表概括成如下的链表结构: 1.在一个头结点+更小的链表基础上,从更小的链表中删除指定元素,得到一个全新的链表--图中红丝的方块. 此时我们需要关心如何
Java实现链表中元素的获取、查询和修改方法详解

本文实例讲述了Java实现链表中元素的获取.查询和修改方法.分享给大家供大家参考,具体如下: 本节是在上一小节Java链表中添加元素的基础上继续完善我们的链表相关方法的编写,在本节中我们着重对如何获取链表中元素.查询元素以及修改元素进行学习. 一.获取元素 1.关于获取链表中元素的方法的分析由于我们使用了虚拟头结点,而我们每次都需要从第一个真实节点开始,因此需要首先得到虚拟头结点的下一个节点是谁,然后在此基础上进行遍历工作,相关代码如下: //获取链表的第index(0-based)个位置的元
Java针对封装数组的简单复杂度分析方法

本文实例讲述了Java针对封装数组的简单复杂度分析方法.分享给大家供大家参考,具体如下: 完成了数组的封装之后我们还需对其进行复杂度分析: 此处的复杂度分析主要是指时间复杂度分析,算法的时间复杂度反映了程序执行时间随输入规模增长而增长的量级,在很大程度上能很好反映出算法的优劣与否. 1.简单概念在各种不同算法中,若算法中语句执行次数为一个常数,则时间复杂度为O(1),另外,在时间频度不相同时,时间复杂度有可能相同,如T(n)=n2+3n+4与T(n)=4n2+2n+1它们的频度不同,但时间复杂
Java链表中元素删除的实现方法详解【只删除一个元素情况】

本文实例讲述了Java链表中元素删除的实现方法.分享给大家供大家参考,具体如下: 该部分与上一节是息息相关的,关于如何在链表中删除元素,我们一步一步来分析: 一.图示删除逻辑假设我们需要在链表中删除索引为2位置的元素,此时链表结构为: 若要删除索引为2位置的元素,需要获取索引为2位置的元素之前的前置节点(此时为索引为1的位置的元素),因此我们需要设计一个变量prev来记录前置节点. 1.初始时变量prev指向虚拟头结点dummyHead: 2.寻找到前置节点位置,(对于该例子前置节点为索引为1

Java实现删除排序链表中的重复元素的方法

相关推荐

随机推荐