Leetcode 1836. Remove Duplicates From an Unsorted Linked List Solution

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.

Example 1:

Input: head = [1,2,3,2] Output: [1,3] Explanation: 2 appears twice in the linked list, so all 2's should be deleted. After deleting all 2's, we are left with [1,3].

Example 2:

Input: head = [2,1,1,2] Output: [] Explanation: 2 and 1 both appear twice. All the elements should be deleted.

Example 3:

Input: head = [3,2,2,1,3,2,4] Output: [1,4] Explanation: 3 appears twice and 2 appears three times. After deleting all 3's and 2's, we are left with [1,4].

Constraints:

• The number of nodes in the list is in the range [1, 105]
• 1 <= Node.val <= 105

Approach

The basic idea is to traverse the linked list and maintain a count of each value in the list. Then, traverse the list again to delete nodes with values that appear more than once.

1. Create a dummy node dummy, with value 0, and point it to the head of the list.
2. Create an unordered_map count to store the count of each value in the list.
3. Traverse the linked list and increment the count for each value in the map.
4. Traverse the list again with a pointer curr, starting at the dummy node:
   1. While curr->next is not NULL and its value appears more than once in the count map, delete the node.
   2. Move curr to the next node.
5. Return the next node of the dummy node as the new head.

Example

Given the input linked list: [1, 2, 3, 2] After counting the values, the map count will be: {1: 1, 2: 2, 3: 1}

During the second traversal:

1Initial list: 0 -> 1 -> 2 -> 3 -> 2
2              dummy      curr
3
4Updated list: 0 -> 1 -> 3 -> 2
5              dummy  curr

The final output will be: [1, 3]

Solution in C++

1class Solution {
2public:
3    ListNode* deleteDuplicatesUnsorted(ListNode* head) {
4        ListNode dummy(0, head);
5        unordered_map<int, int> count;
6
7        for (ListNode* curr = head; curr; curr = curr->next)
8            ++count[curr->val];
9
10        ListNode* curr = &dummy;
11
12        while (curr) {
13            while (curr->next && count.count(curr->next->val) &&
14                   count[curr->next->val] > 1)
15                curr->next = curr->next->next;
16            curr = curr->next;
17        }
18
19        return dummy.next;
20    }
21};

Solution in Python

1class Solution:
2    def deleteDuplicatesUnsorted(self, head: Optional[ListNode]) -> Optional[ListNode]:
3        dummy = ListNode(0, head)
4        count = {}
5        
6        curr = head
7        while curr:
8            count[curr.val] = count.get(curr.val, 0) + 1
9            curr = curr.next
10            
11        curr = dummy
12        while curr:
13            while curr.next and count.get(curr.next.val, 0) > 1:
14                curr.next = curr.next.next
15            curr = curr.next
16                
17        return dummy.next

Solution in Java

1class Solution {
2    public ListNode deleteDuplicatesUnsorted(ListNode head) {
3        ListNode dummy = new ListNode(0, head);
4        HashMap<Integer, Integer> count = new HashMap<>();
5
6        ListNode curr = head;
7        while (curr != null) {
8            count.put(curr.val, count.getOrDefault(curr.val, 0) + 1);
9            curr = curr.next;
10        }
11
12        curr = dummy;
13        while (curr != null) {
14            while (curr.next != null && count.get(curr.next.val) > 1) {
15                curr.next = curr.next.next;
16            }
17            curr = curr.next;
18        }
19        return dummy.next;
20    }
21}

Solution in JavaScript

1class ListNode {
2    constructor(val, next) {
3        this.val = val;
4        this.next = next;
5    }
6}
7
8class Solution {
9    deleteDuplicatesUnsorted(head) {
10        const dummy = new ListNode(0, head);
11        const count = new Map();
12
13        let curr = head;
14        while (curr) {
15            count.set(curr.val, (count.get(curr.val) || 0) + 1);
16            curr = curr.next;
17        }
18
19        curr = dummy;
20        while (curr) {
21            while (curr.next && count.get(curr.next.val) > 1) {
22                curr.next = curr.next.next;
23            }
24            curr = curr.next;
25        }
26        return dummy.next;
27    }
28}

Solution in C#

1public class ListNode {
2    public int val;
3    public ListNode next;
4    public ListNode(int val=0, ListNode next=null) {
5        this.val = val;
6        this.next = next;
7    }
8}
9
10public class Solution {
11    public ListNode DeleteDuplicatesUnsorted(ListNode head) {
12        ListNode dummy = new ListNode(0, head);
13        Dictionary<int, int> count = new Dictionary<int, int>();
14
15        ListNode curr = head;
16        while (curr != null) {
17            count[curr.val] = count.GetValueOrDefault(curr.val, 0) + 1;
18            curr = curr.next;
19        }
20
21        curr = dummy;
22        while (curr != null) {
23            while (curr.next != null && count[curr.next.val] > 1) {
24                curr.next = curr.next.next;
25            }
26            curr = curr.next;
27        }
28        return dummy.next;
29    }
30}

In conclusion, the problem of finding and deleting duplicate nodes in an unsorted linked list can be solved using a two-pass approach. First, traverse the list and count the occurrences of each value. Then, traverse the list again, deleting nodes with values that appear more than once. Implementations in C++, Python, Java, JavaScript, and C# have been provided, demonstrating the use of a dummy node, hash data structures, and basic linked list manipulation techniques.