Problem

Given the head of a linked list, find all the values that appear more than once in the list and delete the nodes that have any of those values.

Return the linked list after the deletions.

Examples

Example 1:

1
2

Input: head = [1,2,3,3,4,4,5]
Output: [1,2,5]

Example 2:

1
2

Input: head = [1,1,1,2,3]
Output: [2,3]

This problem is similar to Remove duplicates from Sorted List 2, but here array is not sorted. Also, it is similar to Remove duplicates from an unsorted linked list keeping only one instance, but here we don’t keep any duplicates, and in that problem we keep only one copy of element in the end.

Solution

Method 1 - Using Frequency Map

We can use a hash map cnt to count the occurrences of each element in the linked list and then traverse the list to remove elements that appear more than once.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
    public ListNode deleteDuplicatesUnsorted(ListNode head) {
        Map<Integer, Integer> cnt = new HashMap<>();
        for (ListNode cur = head; cur != null; cur = cur.next) {
            cnt.put(cur.val, cnt.getOrDefault(cur.val, 0) + 1);
        }
        ListNode dummy = new ListNode(0, head);
        for (ListNode pre = dummy, cur = head; cur != null; cur = cur.next) {
            if (cnt.get(cur.val) > 1) {
                pre.next = cur.next;
            } else {
                pre = cur;
            }
        }
        return dummy.next;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution:
    def deleteDuplicatesUnsorted(self, head: ListNode) -> ListNode:
        cnt = Counter()
        cur = head
        while cur:
            cnt[cur.val] += 1
            cur = cur.next
        dummy = ListNode(0, head)
        pre, cur = dummy, head
        while cur:
            if cnt[cur.val] > 1:
                pre.next = cur.next
            else:
                pre = cur
            cur = cur.next
        return dummy.next

Complexity

  • ⏰ Time complexity: O(n) where n is the length of linked list
  • 🧺 Space complexity: O(n) for using the hashmap