> For the complete documentation index, see [llms.txt](https://zhenchaogan.gitbook.io/leetcode-solution/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://zhenchaogan.gitbook.io/leetcode-solution/leetcode-1836-remove-duplicates-from-an-unsorted-linked-list.md).

# LeetCode 1836. Remove Duplicates From an Unsorted Linked List

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:**![](https://assets.leetcode.com/uploads/2021/04/21/tmp-linked-list.jpg)

```
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:**![](https://assets.leetcode.com/uploads/2021/04/21/tmp-linked-list-1.jpg)

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

**Example 3:**![](https://assets.leetcode.com/uploads/2021/04/21/tmp-linked-list-2.jpg)

```
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, 10^5]`
* `1 <= Node.val <= 10^5`

## Solution

```
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* deleteDuplicatesUnsorted(ListNode* head) {
        ListNode sudo_head(-1);
        
        unordered_map<int, int> mymap;
        for (ListNode* tmp = head; tmp != nullptr; tmp = tmp->next) {
            mymap[tmp->val]++;
        }
        
        ListNode* p = &sudo_head;
        for (ListNode* tmp = head; tmp != nullptr; tmp = tmp->next) {
            if (mymap[tmp->val] > 1) {
                continue;
            }
            
            p->next = tmp;
            p = tmp;
        }
        p->next = nullptr;
        
        return sudo_head.next;
    }
};
```