83. 删除排序链表中的重复元素

Wesley13
• 阅读 493

题目描述

题目地址:https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list/

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

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

示例 2:

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

利用Set

这题的要求是去除重复的元素,既然是去重,那么有一种数据结构就可以派上用场。Set,我们将链表中的元素遍历一遍,放到Set中,这样就自动去重了。  

83. 删除排序链表中的重复元素

需要注意,Set存入进去的时候是不保证顺序的,如果要让Set中元素按照插入的顺序存放,可以使用LinkedHashSet这样的类来完成。

class Solution {    public ListNode deleteDuplicates(ListNode head) {        LinkedHashSet s = new LinkedHashSet();        //遍历链表,将元素放入LinkedHashSet        //此时的s变量中保存的就是去重的元素了                //遍历 s,将元素取出        int[] arr = 。。。。        //遍历链表,修改链表中元素的值    }}

上面我没有做具体实现,只写了一些注释。因为上面那种实现方式在面试的时候是无法通过的,如果你这么写了,面试官会继续追问,如何不利用API自己去重。
面试的时候你可以选说出上面的那种实现方式,虽然不是最优解,但可以实现要求。上面那种方式实现起来很简单,先把最简单的实现方式说出来,缓解一下情绪也是不错的,等面试官继续追问后,再说出更优解。
所以上面那个代码我就不实现啦,感兴趣的同学们可以自行实现一下,下面我们来说说如何不利用库函数的方式,一遍遍历完成去重。

一次遍历解法

一次遍历的方式,需要用a和b两个指针,然后b指针不断往前走,如果a指针和b指针的元素相等则啥都不做;如果a指针和b指针的元素不等,则a指针也往前走一位,并将b指针的值赋给a指针。
空说不好理解,下面是动态实例图:

83. 删除排序链表中的重复元素

java的实现代码如下:

class Solution {    public ListNode deleteDuplicates(ListNode head) {        if(head==null || head.next==null) {            return head;        }        ListNode i = head;        ListNode j = head;        while(j!=null) {            if(i.val==j.val) {                //i和j相当,啥都不做,j继续前进                j = j.next;            }            else {                //i 指向下一个元素                i = i.next;                i.val = j.val;                //j继续前进                j = j.next;            }        }        i.next = null;        return head;    }}

上面的if和else其实可以精简一下,于是代码就变成这样了:

class Solution {    public ListNode deleteDuplicates(ListNode head) {        if(head==null || head.next==null) {            return head;        }        ListNode i = head;        ListNode j = head;        while(j!=null) {            //如果i不等于j,则i前进一位,然后将j的值赋给i            if(i.val!=j.val) {                i = i.next;                i.val = j.val;            }            //不管i是否等于j,j每次都前进一位            j = j.next;        }        i.next = null;        return head;    }}

python的实现如下:

class Solution(object):    def deleteDuplicates(self, head):        """        :type head: ListNode        :rtype: ListNode        """        if not (head and head.next):            return head        i,j = head,head        while j:            if i.val!=j.val:                i = i.next                i.val = j.val            j = j.next        i.next = None        return head

(全文完)

83. 删除排序链表中的重复元素

本文分享自微信公众号 - 大话算法(algorithm2pic)。
如有侵权,请联系 support@oschina.cn 删除。
本文参与“OSC源创计划”,欢迎正在阅读的你也加入,一起分享。

点赞
收藏
评论区
推荐文章
blmius blmius
2年前
MySQL:[Err] 1292 - Incorrect datetime value: ‘0000-00-00 00:00:00‘ for column ‘CREATE_TIME‘ at row 1
文章目录问题用navicat导入数据时,报错:原因这是因为当前的MySQL不支持datetime为0的情况。解决修改sql\mode:sql\mode:SQLMode定义了MySQL应支持的SQL语法、数据校验等,这样可以更容易地在不同的环境中使用MySQL。全局s
皕杰报表之UUID
​在我们用皕杰报表工具设计填报报表时,如何在新增行里自动增加id呢?能新增整数排序id吗?目前可以在新增行里自动增加id,但只能用uuid函数增加UUID编码,不能新增整数排序id。uuid函数说明:获取一个UUID,可以在填报表中用来创建数据ID语法:uuid()或uuid(sep)参数说明:sep布尔值,生成的uuid中是否包含分隔符'',缺省为
CuterCorley CuterCorley
3年前
Python 列表 使用技巧
@toc1.列表表达式与列表排序列表中的元素也是可迭代的对象如列表、元组等时,要根据这些元素的某个子元素对列表排序,常规排序方式失效,需要用sorted()函数并指定key。题目:输入一组数到列表nums,请找到列表中任意两个元素相加能够等于9的元素,形成一个元组,使其小数在前大数在后,如:(2,7),(1,8)。重复的元组元素只保留一个,结
待兔 待兔
1星期前
手写Java HashMap源码
HashMap的使用教程HashMap的使用教程HashMap的使用教程HashMap的使用教程HashMap的使用教程22
Stella981 Stella981
2年前
KVM调整cpu和内存
一.修改kvm虚拟机的配置1、virsheditcentos7找到“memory”和“vcpu”标签,将<namecentos7</name<uuid2220a6d1a36a4fbb8523e078b3dfe795</uuid
Wesley13 Wesley13
2年前
82. 删除排序链表中的重复元素 II
!(https://img2020.cnblogs.com/blog/947397/202005/94739720200516124452599945168267.png)!(https://img2020.cnblogs.com/blog/947397/202005/947397202005161245009921440374123.
Stella981 Stella981
2年前
279. 完全平方数 leetcode JAVA
题目:给定正整数 _n_,找到若干个完全平方数(比如 1,4,9,16,...)使得它们的和等于_n_。你需要让组成和的完全平方数的个数最少。示例 1:输入:_n_12输出:3解释:12444.示例2:输入:_n_13输出:2解释:134
Stella981 Stella981
2年前
LeetCode 92. 反转链表 II(Reverse Linked List II)
题目描述反转从位置_m_到_n_的链表。请使用一趟扫描完成反转。说明:1≤ _m_ ≤ _n_ ≤链表长度。示例:输入:12345NULL,m2,n4输出:14325NULL解题思路本题类似于反转链表
Stella981 Stella981
2年前
LeetCode:283.移动零——简单
题目:283.移动零:给定一个数组nums,编写一个函数将所有0移动到数组的末尾,同时保持非零元素的相对顺序。示例:输入:0,1,0,3,12输出:1,3,12,0,0说明:1.必须在原数组上操作,不能拷贝额外的数组。2.尽量减少操作
Wesley13 Wesley13
2年前
279,对链表进行插入排序
对链表进行插入排序。!(https://oscimg.oschina.net/oscnet/9dfd592075eb9c212bf1eabe9e8ecb60522.gif)插入排序的动画演示如上。从第一个元素开始,该链表可以被认为已经部分排序(用黑色表示)。每次迭代时,从输入数据中移除一个元素(用红色表示),并原地将其插入到已排好序的链表中。