82. Remove Duplicates from Sorted List II

Leetcode Linked List

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

Example 1:

Input: 1->2->3->3->4->4->5
Output: 1->2->5

Example 2:

Input: 1->1->1->2->3
Output: 2->3

/**
 * Given a sorted linked list, delete all nodes that have duplicate numbers,
 * leaving only distinct numbers from the original list.
 *
 * https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/description/
 *
 * 与 Q83RemoveDuplicatesFromSortedList 非常类似，需要注意的有两点：
 * 1. 头部元素重复时，需要直接删除头部元素，所以引入了dummy listnode，这样可以不考虑这种特殊情况
 * 2. 其他元素重复时，需要遍历直到所有元素都删除干净，小心指针的处理
 *
 */

public class Q82RemoveDuplicatesFromSortedListII {
    public static ListNode deleteDuplicates(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }

        ListNode dummy = new ListNode(0);
        dummy.next = head;

        ListNode pos = head, prev = dummy;
        while ((pos != null) && (pos.next != null)) {
            if (pos.val == pos.next.val) {
                while ((pos.next != null) && (pos.val == pos.next.val)) {
                    pos = pos.next;
                }
                pos = pos.next;
                prev.next =  pos;
            } else {
                prev = pos;
                pos = pos.next;
            }
        }

        return dummy.next;
    }
}