/* Use a HashSet to record whether a val has appeared or not. We assume that the linked list is singly linkedand the val stored is integer, this can be asked during the interview. The time complexity is O(N) and spacecomplexity is O(N)In the Follow up, we could ask if the linked list could be destroy or not, if permitted, we could sort the linkedlist and then pass the list one time, the time complexity could be O(NlogN) and space complexity could be O(1).Here we assume not destroy the linked list, we use two pointer, the first pointer would pointed to a node thatmight have duplicates on its right side and use the second one to iterate the right side to remove them, then forward the first pointer, the left side of first pointer would guarantee that there are no duplicates. The timecomplexity is O(N2) and space complexity is O(1).*/import java.util.*;public class RemoveDuplicateLinkList {    public void removeDuplicate(Node head) {        //Use a sentinel to handle null situation        Node sent = new Node(0); sent.next = head;        HashSet<Integer> set = new HashSet<Integer>();        Node temp = sent;        while(temp != null) {            if(temp.next != null) {                // If a value has not showed yet, record it and forward the pointer to check new value                if(set.contains(temp.next.val) == false) {                    set.add(temp.next.val); temp = temp.next;                }                else {                    // If it has showed, remove it, but do not forward the pointer, since the value is new already                    temp.next = temp.next.next;                }            }            else {                temp = temp.next;            }        }    }    public void removeDuplicate2(Node head) {        Node first = head, second = head;        while(first != null) {            // A new node that might have depulicate, we need to pass the right side            second = first;            while(second != null) {                if(second.next != null) {                    if(second.next.val == first.val) {                        second.next = second.next.next;                    }                    else {                        second = second.next;                    }                }                else {                    second = second.next;                }            }            first = first.next;        }    }    public void print(Node head) {        Node temp = head;        while(temp != null) {            System.out.print(temp.val + " ");            temp = temp.next;        }        System.out.println("");    }    public static void main(String[] args) {        Node node1 = new Node(1); Node node11 = new Node(1); Node node111 = new Node(1);        Node node2 = new Node(2); Node node22 = new Node(2); Node node3 = new Node(3);        node1.next = node11; node11.next = node2; node2.next = node111; node111.next = node3; node3.next = node22;        Node head = node22;        RemoveDuplicateLinkList rd = new RemoveDuplicateLinkList();        rd.removeDuplicate2(head); rd.print(head);    }}