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

题目描述

题目地址: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中,这样就自动去重了。  

需要注意,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指针。
空说不好理解,下面是动态实例图:

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

(全文完)

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

评论

暂无评论