leetcode 82.删除排序链表中的重复元素 II
题目描述
给定一个排序链表,删除所有含有重复数字的节点,只保留原始链表中 没有重复出现 的数字。
示例 1:
输入: 1->2->3->3->4->4->5
输出: 1->2->5
示例 2:
输入: 1->1->1->2->3
输出: 2->3
解法一
有时候当我们拿到一道题时,如果不能立马想到比较好的解决方案,不妨先用”笨”一点的方式去做一下,”笨”的方案虽然效率不高,但是实现起来简单,也容易想到,为后面再做优化也起到了一个铺垫的效果。
这里要求的是去重,那简单。用一个哈希表记录每个值出现的频率就可以了。
具体做法如下:
-
遍历链表,将每个节点的值放到哈希表中,哈希表的key就是节点的值,value是这个值出现的频率 -
遍历哈希表,将所有频率==1的key放到集合中 -
对集合进行排序 -
遍历集合,然后不断创建新的链表节点
当然这里可以优化一下,比如使用LinkedHashMap
或者OrderedDict
这样的数据结构,可以省去排序环节。
java代码:
class Solution { public ListNode deleteDuplicates(ListNode head) { if(head==null || head.next==null) { return head; } //用哈希表记录每个节点值的出现频率 HashMap<Integer,Integer> cache = new HashMap<Integer,Integer>(); ArrayList<Integer> arr = new ArrayList<Integer>(); ListNode p = head; while(p!=null) { int val = p.val; if(cache.containsKey(val)) { cache.put(val,cache.get(val)+1); } else { cache.put(val,1); } p = p.next; } //将所有只出现一次的值放到arr中,之后再对这个arr排序 for(Integer k : cache.keySet()) { if(cache.get(k)==1) { arr.add(k); } } Collections.sort(arr); ListNode dummy = new ListNode(-1); p = dummy; //创建长度为arr.length长度的链表,依次将arr中的值赋给每个链表节点 for(Integer i : arr) { ListNode tmp = new ListNode(i); p.next = tmp; p = p.next; } return dummy.next; } }
python代码:
class Solution(object): def deleteDuplicates(self, head): if not (head and head.next): return head # 用哈希表记录每个节点值的出现频率 d = dict() p = head arr = [] while p: val = p.val d[val] = d.setdefault(val,0)+1 p = p.next # 将所有只出现一次的值放到arr中,之后再对这个arr排序 for k in d: if d[k]==1: arr.append(k) arr = sorted(arr) dummy = ListNode(-1) p = dummy # 创建长度为len(arr)长度的链表,依次将arr中的值赋给每个链表节点 for i in arr: tmp = ListNode(i) p.next = tmp p = p.next return dummy.next
解法二
这里我们使用双指针的方式,定义a
,b
两个指针。
考虑到一些边界条件,比如1->1->1->2
这种情况,需要把开头的几个1
给去掉,我们增加一个哑结点,方便边界处理。
初始的两个指针如下:
-
将 a
指针指向哑结点 -
将 b
指针指向head
(哑结点的下一个节点)
如果a
指向的值不等于b
指向的值,则两个指针都前进一位
否则,就单独移动b
,b
不断往前走,直到a
指向的值不等于b
指向的值。
注意,这里不是直接比较a.val==b.val
,这么比较不对,因为初始的时候,a
指向的是哑结点,所以比较逻辑应该是这样:
a.next.val == b.next.val
当两个指针指向的值相等时,b
不断往前移动,这里是通过一个while
循环判断的,因为要过滤掉1->2->2->2->3
重复的2
。
那么整个逻辑就是两个while
,但时间复杂度不是O(N^2),而是O(N),空间上也只是常数级别。
具体执行的动态如如下:
动态图中如果某一步执行太快没看清,可以看下面的静态图,由于没法用幻灯片演示,这里我将每一步的执行过程都整合到一起了。点击文章最下方的【阅读原文】有幻灯片版本的演示(需要在电脑端才能正常显示):
java代码:
class Solution { public ListNode deleteDuplicates(ListNode head) { if(head==null || head.next==null) { return head; } ListNode dummy = new ListNode(-1); dummy.next = head; ListNode a = dummy; ListNode b = head; while(b!=null && b.next!=null) { //初始化的时a指向的是哑结点,所以比较逻辑应该是a的下一个节点和b的下一个节点 if(a.next.val!=b.next.val) { a = a.next; b = b.next; } else { //如果a、b指向的节点值相等,就不断移动b,直到a、b指向的值不相等 while(b!=null && b.next!=null && a.next.val==b.next.val) { b = b.next; } a.next = b.next; b = b.next; } } return dummy.next; } }
python代码:
class Solution(object): def deleteDuplicates(self, head): if not (head and head.next): return head dummy = ListNode(-1) dummy.next = head a = dummy b = head while b and b.next: # 初始化的时a指向的是哑结点,所以比较逻辑应该是a的下一个节点和b的下一个节点 if a.next.val!=b.next.val: a = a.next b = b.next else: # 如果a、b指向的节点值相等,就不断移动b,直到a、b指向的值不相等 while b and b.next and a.next.val==b.next.val: b = b.next a.next = b.next b = b.next return dummy.next
解法三
解法三和解法二的代码实现很类似,区别是
解法二初始化的时候b
指针指向的是head
而解法三初始化的时候b
指针指向的是head.next
所以判断两个指针指向的节点值是否相等时,解法三是这么做的:
a.next.val == b.val
当两个指针指向的值不同时,a
和b
指针都是前移一位
当两个指针指向的值相同时,解法二和解法三也略有不同
主要体现在while
循环后面的几句
此外b
指针还需要考虑边界条件,当循环结束后b
指针可能会指向空,所以不能直接b=b.next
,需要判断一下边界,这里请查看代码,并配合动态/静态图方便理解。
时间复杂度和空间复杂度,解法二和解法三都是一样的。
动画演示如下:
下面是静态长图:
代码实现中还有一个小细节,外层的while
是这么写的
while(b!=null)
如果写成
while(b!=null && b.next!=null)
这就不对了,没法处理1->1
这种情况。
java代码:
class Solution { public ListNode deleteDuplicates(ListNode head) { if(head==null || head.next==null) { return head; } ListNode dummy = new ListNode(-1); dummy.next = head; ListNode a = dummy; ListNode b = head.next; while(b!=null) { if(a.next.val!=b.val) { a = a.next; b = b.next; } else { while(b!=null && a.next.val==b.val) { b = b.next; } //这里的去重跟解法二有点差别,解法二的是 //a.next = b.next a.next = b; //b指针在while中判断完后,可能指向了null,这里需要处理边界问题 b = (b==null) ? null : b.next; } } return dummy.next; } }
python代码:
class Solution(object): def deleteDuplicates(self, head): if not (head and head.next): return head dummy = ListNode(-1) dummy.next = head a = dummy b = head.next while b: if a.next.val!=b.val: a = a.next b = b.next else: while b and a.next.val==b.val: b = b.next # 这里的去重跟解法二有点差别,解法二的是 # a.next = b.next a.next = b # b指针在while中判断完后,可能指向了null,这里需要处理边界问题 b = b.next if b else None return dummy.next
(全文完)
One thought on “leetcode 82.删除排序链表中的重复元素 II”
You will also be able to network with other bloggers, creating a support group which will help you attain even greater success in the future. Lorna Ross Johnstone