[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:

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

从一个未排序的链表中移除重复的节点。

题意是给一个单链表，链表中的 node.val 是乱序的，请你找到那些 val 出现次数超过一次的 node 并将他们删去，返回删除后的链表。

思路是需要扫描两遍，这里我们同时需要一个 hashmap 记录每个不同 node.val 的出现次数。第一遍扫描的时候记录每个不同 node.val 的出现次数，第二遍扫描的时候，需要创建一个新的 dummy 节点，用dummy.next去试探下一个节点是否是需要删除的节点，如果是，就直接跳过即可。

时间O(n)

空间O(n)

Java实现

 1 /**
 2  * Definition for singly-linked list.
 3  * public class ListNode {
 4  *     int val;
 5  *     ListNode next;
 6  *     ListNode() {}
 7  *     ListNode(int val) { this.val = val; }
 8  *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 9  * }
10  */
11 class Solution {
12     public ListNode deleteDuplicatesUnsorted(ListNode head) {
13         // HashMap<Integer, Integer> map = new HashMap<>();
14         int[] map = new int[(int) Math.pow(10, 5) + 1];
15         // dummy - 最后需要return用的
16         // dummy2 - 第二遍扫描的时候需要用的，因为涉及到删除操作，所以只能用.next试探
17         ListNode dummy = new ListNode(0);
18         ListNode dummy2 = dummy;
19         dummy.next = head;
20 
21         ListNode cur = head;
22         while (cur != null) {
23             // map.put(cur.val, map.getOrDefault(cur.val, 0) + 1);
24             map[cur.val]++;
25             cur = cur.next;
26         }
27 
28         while (dummy2.next != null) {
29             // if (map.getOrDefault(dummy2.next.val, 0) > 1) {
30             if (map[dummy2.next.val] > 1) {
31                 dummy2.next = dummy2.next.next;
32             } else {
33                 dummy2 = dummy2.next;
34             }
35         }
36         return dummy.next;
37     }
38 }