82. Remove Duplicates from Sorted List II

# medium

Key idea: skip all same elements until different one then move forward

核心：跳过所有相同的元素，直到碰到不同的元素再继续往前走

Solution 1(complicated version):

very complicated

English

1. head points current node, once head.val == head.next.val, it deletes all duplicates except itself.

2. pre records pre-node of head and helps delete the first duplicates.

3. if not encounter duplicates, both of pre and head move one step.

Dummy note and pre-node are necessary. flag is needed to judge head is the last duplicate or nor. When last node is duplicate node, don't forget to let pre.next = null because pre represents the whole new list.

Chinese

Solution 2(easy version):

simple approach

English

1. head represents new list.

2. record duplicates value and delete all duplicates until head.next.val != head.next.next.val.

3. otherwise head move one step.

Don't move head until ensure the next element is not duplicated.

Chinese

If deleting all duplicates required, we can record the value and delete them in on time; If deleting all duplicates except itself required, we can keep first one and delete others.

如果要删除所有重复，那么可以记录下这个值并且一次性删除所有重复；如果删除所有重复但要保留一个，那么可以只保留第一个然后删掉所有后面出现的重复

Java

class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        ListNode dump = new ListNode();
        dump.next = head;
        ListNode pre = dump;
        ListNode curr = head;
        boolean isDuplicate = false;
        while(curr != null && curr.next != null) {
            ListNode currNext = curr.next;
            if(curr.val == currNext.val)
                isDuplicate = true;
            else {
                if(isDuplicate == false) {
                    pre.next = curr;
                    pre = curr;
                } else {
                    isDuplicate = false;
                }
            }
            curr = curr.next;
        }
        
        // deal with the last node
        if(isDuplicate)
            pre.next = null;
        else
            pre.next = curr;
        
        return dump.next;
    }
}

Python