forked from algorithm001/algorithm
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathLeetCode_83_139.java
More file actions
76 lines (63 loc) · 2.89 KB
/
Copy pathLeetCode_83_139.java
File metadata and controls
76 lines (63 loc) · 2.89 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
//https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list/
//Given a sorted linked list, delete all duplicates such that each element appear only once.
//1，前后节点比对（注意发生重复时，pre保持不变。不重复时，pre前移）
//执行用时 : 2 ms, 在Remove Duplicates from Sorted List的Java提交中击败了57.30% 的用户
//内存消耗 : 36.5 MB, 在Remove Duplicates from Sorted List的Java提交中击败了68.83% 的用户
class Solution {
public ListNode deleteDuplicates(ListNode head) {
if (head == null) return head; //防止 head为null
ListNode p = head.next;
ListNode pre = head;
while( p != null ){
if (pre.val == p.val){
pre.next = p.next;
p = p.next;
}
else{
pre = p;
p = p.next;
}
}
return head;
}
}
//java.lang.NullPointerException具体意思是空指针异常，最常见的问题就是没有初始化。
//字符串等数据类型没有初始化，例：链表中的字符代码没加 if (head == null) return head;
//2，set做法（适合无序链表）
//执行用时 : 7 ms, 在Remove Duplicates from Sorted List的Java提交中击败了5.10% 的用户
//内存消耗 : 36.3 MB, 在Remove Duplicates from Sorted List的Java提交中击败了75.05% 的用户
class Solution {
public ListNode deleteDuplicates(ListNode head) {
Set<Object> set = new HashSet<>();
ListNode pre = new ListNode(-1);
pre.next = head;
ListNode p = head;
while( p != null ){
if (set.contains(p.val)){
pre.next = p.next;
p = p.next;
}
else{
set.add(p.val);
pre = p;
p = p.next;
}
}
return head;
}
}
//3，递归（时间效率很差）
//执行用时 : 3 ms, 在Remove Duplicates from Sorted List的Java提交中击败了6.53% 的用户
//内存消耗 : 36.3 MB, 在Remove Duplicates from Sorted List的Java提交中击败了74.62% 的用户
class Solution {
public ListNode deleteDuplicates(ListNode head) {
if (head == null || head.next == null) return head;
ListNode p = deleteDuplicates(head.next);
if (head.val == p.val) head.next = p.next;
return head;
}
}
//1,找终止条件：当head指向链表只剩一个元素的时候，自然是不可能重复的，因此return
//2,想想应该返回什么值：应该返回的自然是已经去重的链表的头节点
//3,每一步要做什么：宏观上考虑，此时head.next已经指向一个去重的链表了，而根据第二步，我应该返回一个去重的链表的头节点。
//因此这一步应该做的是判断当前的head和head.next是否相等，如果相等则说明重了，返回head.next，否则返回head