082.Remove Duplicates from Sorted List II

Posted on | In

Test cases

1
2
3
4
5
6
7
[]
[1,1]
[1,1,2]
[1,1,2,2]
[1,2,2,3]
[1,2,2,3,3]
[1,2,3,4,5]

Solution 1: accepted 1ms

Try to use only ListNode

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
public ListNode deleteDuplicates(ListNode head) {
    ListNode pointer = head;
    ListNode previous = null;
    while (pointer != null) {    
        ListNode fast = pointer.next;
        boolean duplicate = false;
        while (fast != null && pointer.val == fast.val) {
            fast = fast.next;
            duplicate = true;
        }
        if (!duplicate) {
            previous = pointer;
        } else {
            if (previous == null) { // [1,1,...]
                head = fast;
            } else {
                previous.next = fast; // [1,2,2,3...]
            }
        }
        pointer = fast;
    }
    return head;
}

Solution 2: accepted 1ms

Use a virtual node to help organize the list

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public ListNode deleteDuplicates(ListNode head) {        
    ListNode virtualHead = new ListNode(0);
    virtualHead.next = head;
    ListNode pre = virtualHead;
    ListNode cur = head;
    while (cur != null) {                
        while (cur.next != null && cur.val == cur.next.val) {
            cur = cur.next;
        }
        if (pre.next == cur) { // if both pre and cur point to the same node (no duplicates detected)
            pre = cur; // simply move on
        } else { 
            pre.next = cur.next; // skip points in between
        }
        cur = cur.next; // move on
    }
    return virtualHead.next;
}