Remove Duplicates From an Unsorted Linked List — Leetcode 1836

Original problem link: https://leetcode.com/problems/remove-duplicates-from-an-unsorted-linked-list/description/

In this problem, we’re given a linked list head and asked to remove all nodes with values that have duplicates.

The key point is that we need to be checking the next value in the loop for potential removal and using a dummy head in case the original head is removed. We also should only update curr node when the next is not being removed, since we need to keep checking the new nexts.

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode deleteDuplicatesUnsorted(ListNode head) {
        Map<Integer, Integer> frequencies = new HashMap<>();
        ListNode curr = head;
        while (curr != null) {
            frequencies.put(curr.val, frequencies.getOrDefault(curr.val, 0) + 1);
            curr = curr.next;
        }

        ListNode dummy = new ListNode(0);
        dummy.next = head;
        curr = dummy;
        while (curr != null && curr.next != null) {
            if (frequencies.get(curr.next.val) > 1) {
                // remove curr.next and then we have to test the new next 
                curr.next = curr.next.next;
            } else {
                curr = curr.next;
            }
        }

        return dummy.next;
    }
}

This solution has a runtime between 84–87 ms, which beats 63–81% of submissions in runtime.