1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| class Solution {
public ListNode deleteDuplicates(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode dummy = new ListNode(0);
ListNode curr = head, ptr = head, prev = dummy;
dummy.next = head;
while (curr != null) {
int count = 0;
while (ptr != null && ptr.val == curr.val) {
ptr = ptr.next;
count += 1;
}
if (count > 1) {
prev.next = ptr;
} else {
prev = curr;
}
curr = ptr;
}
return dummy.next;
}
}
|
需要维护一个prev这个pointer以及new一个dummy并指向head, 防止可能出现要移除开头的重复nodes. 如果是间内的话, 用prev就ok了. 因为这里我们要移除所有的重复的, 而不是只保留一个. 因此需要prev这个pointer.
这个加dummy head的方法叫做: Sentinel Head.
时间复杂度: O(n)
空间复杂度: O(1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| class Solution {
public ListNode deleteDuplicates(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode dummy = new ListNode(0);
ListNode curr = head, prev = dummy;
dummy.next = head;
while (curr != null) {
while (curr.next != null && curr.val == curr.next.val) {
curr = curr.next;
}
if (prev.next == curr) {
prev = curr;
} else {
prev.next = curr.next;
}
curr = curr.next;
}
return dummy.next;
}
}
|
这个方法也很好. 就是让curr是否和自己的下一个一样, 如果一样, curr就继续走. 我们需要考虑到curr到达edge case即结尾的时候. 如果curr.next是null的话, 我们访问curr.next.val就是null pointer exception. 于是要加入这个条件即curr.next != null. 此时看prev和curr的相对位置. 如果curr压根没动即prev.next == curr.那么等于是curr下一个值和自己不一样或者下一个值是null, 于是我们让prev = curr即可, 然后更新curr到curr.next. 如果curr移动了, 那说明是找到了一些相同的值. 于是我们让prev.next等于curr.next. 不管curr.next是不同的值还是null, 这样做都是对的. 然后更新curr到curr.next即可.
时间复杂度: O(n)
空间复杂度: O(1)
