Remove Duplicates from Sorted List II | Leetcode

Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.

For example,
Given 1->2->3->3->4->4->5, return 1->2->5.
Given 1->1->1->2->3, return 2->3.

---

Solution: One tricky bit about this question is that when the head element is a duplicate, we have to take care to return the correct value of head, which is not the same one we get from the argument. A convenient way to do this is to create a node "pre" coming before head, so that we will return pre.next no matter whether we remove head or not.

To know whether the elements are duplicates or not, we have to take the next two elements. But you cannot make an element remove itself. The only way to remove an element is to have a reference to the previous element. Hence we use the condition "cur.next.val == cur.next.next.val" instead of "cur.val == cur.next.val" to perform this check.

When there are duplicates, do not advance the current pointer. Otherwise, just advance to the next element.

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        ListNode pre = new ListNode(0);
        pre.next = head;
        
        ListNode cur = pre;
        while (cur.next != null && cur.next.next != null) {
            // If the next two nodes have the same value,
            // then remove them all with the same value.
            if (cur.next.val == cur.next.next.val) {
                int val = cur.next.val;
                cur.next = cur.next.next.next;
                while (cur.next != null && cur.next.val == val) {
                    cur.next = cur.next.next;
                }
            } else {
                cur = cur.next;
            }
        }
        
        return pre.next;
    }
}