LeetCode 1836. Remove Duplicates From an Unsorted Linked List - 链表（Linked List）系列题15

LeetCode 1836. Remove Duplicates From an Unsorted Linked List - 链表（Linked List）系列题15

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

本题也是要求删除链表中有值相同的所有节点，与82. Remove Duplicates from Sorted List II不同的是本题给的链表不是有序的，因此有相同值的节点不一定是连续的。

基本思路就是先找出出现过多次的数值，然后再将对应的节点删掉。可以通过两次遍历来解决，第一次遍历可以用一个hashmap来记录数值出现的次数，第二次遍历把数值出现次数大于1的节点删掉。

注1：头节点有可能被删掉，所有要定义一个preHead.next = head，把头节点当普通节点处理。

注2：在第一次遍历时就可以把再次出现的节点删掉，可以加快第二次遍历的速度。

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def deleteDuplicatesUnsorted(self, head: ListNode) -> ListNode:
        preHead = ListNode(-1, head)
        
        visited = {}
        pre, cur = preHead, head
        while cur:
            if cur.val in visited:
                pre.next = cur.next
                visited[cur.val] += 1
            else:
                pre = cur
                visited[cur.val] = 0
            cur = cur.next
 
        pre, cur = preHead, head
        while cur:
            if visited[cur.val] > 0:
                pre.next = cur.next
            else:
                pre = cur
            cur = cur.next
            
        return preHead.next