1836. Remove Duplicates from An Unsorted Linked List #

题目 #

给定链表头节点 head，找到链表中所有出现 多于一次 的元素，并删除这些元素所在的节点。返回删除后的链表。

思路 #

代码 #

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> map = new HashMap<>();
        ListNode ptr = head;
        while (ptr != null) {
            int times = map.containsKey(ptr.val) == true ? map.get(ptr.val) : 0;
            map.put(ptr.val, times + 1);
            ptr = ptr.next;
        }
        
        ListNode sentinel = new ListNode(-1, head);
        ptr = sentinel;
        while (ptr.next != null) {
            if (map.get(ptr.next.val) > 1) ptr.next = ptr.next.next;
            else ptr = ptr.next;
        }
        
        return sentinel.next;
    }
}