LeetCode - Remove Duplicates from Sorted List II | Darren's Blog

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.
Key Point: Use sentinel node.
头节点也可能被删除。可以使用dummy节点来简化。
http://gongxuns.blogspot.com/2012/12/leetcode-remove-duplicates-from-sorted_11.html

    public ListNode deleteDuplicates(ListNode head) {
        ListNode prev = new ListNode(0);
        prev.next = head;
        head = prev;
        
        ListNode n1=head;
        while(n1.next!=null){
            ListNode n2=n1.next;
            while(n2.next!=null && n2.next.val==n2.val){
                n2=n2.next;
            }
            if(n2!=n1.next){
                n1.next=n2.next;
            }else{
                n1=n1.next;   
            }
        }
        return head.next;
    }

http://www.jiuzhang.com/solutions/remove-duplicates-from-sorted-list-ii/
http://www.programcreek.com/2014/06/leetcode-remove-duplicates-from-sorted-list-ii-java/
Performance may suffer: as too many unnecessary assignment: head.next = head.next.next;

    public ListNode deleteDuplicates(ListNode head) {
        if(head == null || head.next == null)
            return head;
        
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        head = dummy;

        while (head.next != null && head.next.next != null) {
            if (head.next.val == head.next.next.val) {
                int val = head.next.val;
                while (head.next != null && head.next.val == val) {
                    head.next = head.next.next;
                }            
            } else {
                head = head.next;
            }
        }
        
        return dummy.next;
    }

public ListNode deleteDuplicates(ListNode head) {

        if (head == null || head.next == null)

            return head;

        // Use a sentinel node in case the first node will be removed

        ListNode sentinel = new ListNode(0);

        sentinel.next = head;

        ListNode previous = head, current = head.next;

        ListNode lastDistinct = sentinel;   // The last distinct node wrt the current node

        if (previous.val != current.val)

            lastDistinct = head;

        while (current != null) {

            if (current.val != previous.val &&

                    (current.next == null || current.val != current.next.val)) {

                // The current node is a new distinct node; remove all nodes between

                // the last distinct one and it

                lastDistinct.next = current;

                lastDistinct = current;

            }

            previous = current;

            current = current.next;

        }

        lastDistinct.next = null;   // Make sure the list ends properly

        return sentinel.next;

    }

Read full article from LeetCode - Remove Duplicates from Sorted List II | Darren's Blog