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.

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