Leetcode: Remove Duplicates from Sorted List II

 This question is asked at Amazon, Bloomberg, Microsoft, and Adobe. It is as follows:

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

Here are some examples: 

We assume that the list is guaranteed to be sorted in ascending order. 

The approach to solving the problem is through a sentinel head and a processor. Sentinel nodes are widely used for trees and are purely functional and don't hold any data. We can use a pseudo-head with a zero value so that "delete the list head" will never happen. We can tell if a node is a duplicate by comparing its value to the node "after it" in the list. Step by step, this way, we can identify the current sublist of duplicates and delete them through pointer manipulations. The first node in the duplicates sublist is deleted as well, so that means we have to track the predecessor and sentinel nodes simultaneously.

class Solution {

    public ListNode deleteDuplicates(ListNode head) {

        //make a sentinel node

        ListNode sentinel = new ListNode(0, head);

        ListNode pred = sentinel; 

        while(head != null) {

            //move to the first nonduplicate

            if(head.next != null && head.val == head.next.val) {

                head = head.next;

            }

            //delete the duplicate nodes

            pred.next = head.next;

        } else {

            //else move forward in the list.

            pred = pred.next;

        }

         //move the head of the list forward as well. 

        head = head.next;

    }

     //return the first value node

    return sentinel.next;

}