82. Remove Duplicates from Sorted List II

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.

Keep three pointers, first pointer, tail always points to the tail of found list item. second pointer, prev, point to the head of to-be-found list head, and a third pointer, cur, which points the same as prev, while cur and cur's next value are the same, the move forward cur pointer, if cur and prev is not the same, then we need to cut prev to cur off, then move next section of list.

/**
 * 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 dummy = new ListNode(-1);
        dummy.next = head;
        ListNode tail = dummy;
        ListNode prev = head;
        ListNode cur = head;

        while(cur != null && cur.next != null){
            while(cur.next != null && cur.val == cur.next.val){
                cur = cur.next;
            }
            if(cur == prev){
                tail.next = cur;
                tail = tail.next;
            }
            prev = cur.next;
            cur = cur.next;
        }
        tail.next = cur;
        return dummy.next;
    }
}