2021/04/25
遍历法
不用整花里胡哨的链表删除操作，我们另起一个链表，专门搜集那些不重复的元素即可。
对于任意的元素 A[i]，如果 A[i] != A[i-1] && A[i] != A[i+1]，那么 A[i] 需要被收集。
也就是说对于任意的一个结点 A[i]，如果 A [i] == A[i-1] 或者 A[i] == A[i+1] ，则跳过它。
class Solution {
public ListNode deleteDuplicates(ListNode head) {
ListNode sentry = new ListNode(0);
ListNode collector = sentry;
ListNode prev = null;
while (head != null) {
boolean p1 = head.next != null && head.val == head.next.val;
boolean p2 = prev != null && head.val == prev.val;
if (p1 || p2) {
prev = head;
head = head.next;
} else {
ListNode next = head.next;
collector.next = head;
head.next = null; // 注意，当我们在收集结点的时候，一定要记得斩断联系
collector = collector.next;
prev = head;
head = next;
}
}
return sentry.next;
}
}
如果可以引入额外的空间的话，代码可以更加的简化
class Solution {
public ListNode deleteDuplicates(ListNode head) {
ListNode sentry = new ListNode(0);
ListNode collector = sentry;
ListNode prev = null;
while (head != null) {
boolean p1 = head.next != null && head.val == head.next.val;
boolean p2 = prev != null && head.val == prev.val;
if (!p1 && !p2) {
collector.next = new ListNode(head.val); // 这里引入了额外空间
collector = collector.next;
}
prev = head;
head = head.next;
}
return sentry.next;
}
}
递归法
类似第83题的递归方法，只不过如果遇到相同元素，需要在递归之前把这个元素全部消灭掉。
class Solution {
public ListNode deleteDuplicates(ListNode head) {
if (head == null || head.next == null) return head;
if (head.val == head.next.val) {
while (head != null && head.next != null && head.val == head.next.val) {
head = head.next;
}
head = deleteDuplicates(head.next);
} else {
head.next = deleteDuplicates(head.next);
}
return head;
}
}