YSMull
<-- algorithm



原题链接

遍历法

不用整花里胡哨的链表删除操作,我们另起一个链表,专门搜集那些不重复的元素即可。

对于任意的元素 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;
    }
}