LeetCode 1836: Remove Duplicates From an Unsorted Linked List

Explanation:

To remove duplicates from an unsorted linked list, we can use a hash set to keep track of unique values encountered so far. We iterate through the linked list, adding each value to the hash set. If a value is already in the hash set, we remove it from the linked list. This way, we ensure that only unique values remain in the linked list.

Algorithm:

1. Initialize a hash set to store unique values.
2. Initialize two pointers, prev and current, to traverse the linked list.
3. Traverse the linked list:
   • If the current value is not in the hash set, add it to the set and move both pointers to the next node.
   • If the current value is in the hash set, remove the current node by updating prev's next pointer.
4. Return the modified linked list.

Time Complexity: O(N) where N is the number of nodes in the linked list. Space Complexity: O(N) for the hash set to store unique values.

:

public ListNode removeDuplicates(ListNode head) {
    Set<Integer> set = new HashSet<>();
    ListNode dummy = new ListNode(0);
    dummy.next = head;
    ListNode prev = dummy;
    ListNode current = head;
    
    while (current != null) {
        if (!set.contains(current.val)) {
            set.add(current.val);
            prev = current;
        } else {
            prev.next = current.next;
        }
        current = current.next;
    }
    
    return dummy.next;
}