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