Delete duplicates in linked list. O(n) space

DeleteDuplicates.java

package com.interviewbytes.linkedlists;


import java.util.HashMap;
import java.util.Map;

public class DeleteDuplicates {

    public ListNode deleteDuplicates(ListNode head) {

        Map<Integer, Integer> countMap = new HashMap<>();
        ListNode current = head;
        while (current != null) {
            countMap.put(current.val, countMap.getOrDefault(current.val, 0) + 1);
            current = current.next;
        }

        ListNode sentinel = new ListNode(0);
        current = sentinel;

        while (head != null) {
            if (countMap.get(head.val) == 1) {
                current.next = head;
                current = current.next;
            }

            head = head.next;
        }

        current.next = null;

        return sentinel.next;
    }
}

ListNode.java

package com.interviewbytes.linkedlists;

public class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
        val = x;
    }
}